문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 그래프(이산수학) (문단 편집) === 그래프의 동형 === 우선 그래프를 어떤 식으로 표현할 수 있을지를 생각해보자. 단순하게 각 vertice들에 연결된 vertice들의 목록을 기입할 수 있는데, 이를 인접목록이라고 한다. 예를 들면 a,b,c,d,e 라는 vertice들이 있을 때 a는 b,d,e, b는 a, c 등 이런 식으로 단순하게 어떤 점이 어떤 점과 연결되어 있는지를 표로 정리하는 방식이다. 하지만 인접목록으로는 유용한 성질을 유도하기가 어렵다. 이에 각 행,열에 vertice들을 같은 순서대로 나열하고 각 entry들이 vertice들 사이의 연결을 나타내도록 작성하는 방식을 생각할 수 있는데, 이를 인접행렬이라고 하며 이는 인접목록과 비교했을 때 조금 더 유용한 성질들이 있다. 예컨대 단순그래프의 인접행렬은 항상 대칭이고, 단순그래프의 경우에는 대각선이 0이며, 각 vertice에 대응되는 행 또는 열의 모든 숫자를 합치면 degree가 유도되고, 1들의 개수를 2로 나누면 이는 모서리의 개수가 된다는 좋은 성질들이 있다(악수의 정리를 생각해보자). 유사그래프(multigraph, loop가 있는 그래프) 인접행렬의 경우에는 0,1 대신 모서리의 수를 기입하면 되며 loop의 경우에는 대각에 2를 추가해주면 대각선에 0이 들어가는 것을 제외한 위의 대부분의 성질들이 보존된다. 방향성 그래프의 경우에는 행에 있는 vertice들을 시작점으로, 열에 있는 vertice들을 끝점으로 본 후, 예를 들어 1,2,3,4의 vertices 중에서 1이 2로 방향성을 갖고 진행된다면 첫번째 행 두번째 열에는 1을 기입하는 방식을 생각해볼 수 있다.이 경우에 모든 1의 합은 모서리의 개수가 바로 유도된다는 성질을 얻을 수 있다. 특히 인접행렬의 경우, 해당 행렬의 [math(n)] 거듭제곱의 [math(i)]열 [math(j)]행의 값은 꼭짓점 [math(i)]에서 꼭짓점 [math(j)]로 이어지는 길이 [math(n)]의 경로의 수와 같기에, 길이를 아는 경로의 수를 보다 쉽게 계산할 수 있다는 장점도 있다. 또한 결합행렬이라는 방식도 존재한다. 이는 행에는 점들을, 열에는 모서리들을 써둔 후, 점이 모서리와 만날 때만 해당 entry에 1을, 만나지 않는다면 0을 부여하는 방식이다. 이 경우에도 1의 합을 2로 나누면 모서리의 개수가 나오며, 각 열마다 오로지 두개씩의 1만이 나온다. 이는 당연한 건데, 각 모서리는 두개의 끝점 이상을 정의상 가질 수 없기 때문이다. 또한 행의 모든 1을 더하면 차수를 얻을 수 있다. 단 루프가 있는 경우에는 1이 하나만 있을수도 있다. 이는 gilbert strang의 선형대수 교재에서도 사용되는 방식으로, 이를 통해 여러 대상들 사이의 에너지 교환을 행렬로 표현하여 전체 시스템의 변화를 기술하는데에 응용될수도 있다. 보다 자세한 내용은 인접행렬 문서 참조.저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기