고급 수학 1 - 그래프

1. 그래프와 행렬 01. 그래프의 뜻 그래프 : 점과 선으로 이루어진 도형, 점을 꼭짓점이라 하고, 선을 변이라 한다. 꼭짓점의 위치를 바꾸거나 변을 구부리거나 줄여도 두 그래프를 같은 그림으로 그릴 수 있으면 두 그래프는 같은 그래프. 즉, 모양이 같을려면 꼭짓점의 집합과 변의 집합이 각각 같아야 한다. 두 그래프는 같은 그래프 02. 꼭짓점의 차수의 합과 변의 개수 사이의 관계 꼭짓점의 차수 : 그래프에서 한 꼭짓점에 연결된 변의 개수. 그래프에서 각 꼭짓점의 차수를 모두 더할 때 각 변은 그 변의 양 끝 꼭짓점의 차수에서 각각 한 번씩 더해지게 되므로, 그래프의 모든 꼭짓점의 차수의 합은 그래프의 변의 개수의 2배이다. 완전그래프 : 서로 다른 두 꼭짓점 사이에 항상 변이 오직 한 개 있는 그래프 완전그래프에서 꼭짓점의 개수를 n개라 하면, 각 꼭짓점의 차수는 n-1이므로, 변의 개수는 n(n-1)/2 이다. 03. 인접행렬 경로 : 그래프의 한 꼭짓점에서 다른 꼭짓점으로 이...

원문링크 : 고급 수학 1 - 그래프