1703 그래프 와 행렬 1 그래프 의 뜻 점 과 선 으로 이루어진 그림 을 그래프 라고 한다 . 그래프 에서 점 을 꼭짓점 이 라 하 고 , 두 꼭짓점 을 연결 한 선 을 변이 라고 한다 . 
 오른쪽 그래프 에서 꼭짓점 의 집합 은 { A , B , C , D } 이 고 , 변의 집합 A 
 D 은 { AB , AC , AD , BC , CD } 이 다 . 
 C B 
 2 서로 같 은 그래프 두 그래프 에서 꼭짓점 과 변의 연결 상태 가 변하 지 않 도록 하 면서 꼭짓점 의 위치 를 바 꾸 거나 변 을 구부리 거나 늘 이거 나 줄여서 두 그래프 가 같 은 그림 이 될 수 있 으면 두 그 래프 는 서로 같 다고 한다 . 
 3 경로 그래프 의 한 꼭짓점 에서 출발 하 여 연결 된 변 을 따라 한 번 지난 변 을 다시 지나 지 않 으 면서 다른 꼭짓점 으로 이동 하 는 길 을 경로 라고 한다 . 
 4 그래프 를 나타내 는 행렬 n 개 의 점 P ¡, P ™, P £, y , P « 을 꼭짓점 으로 하 는 그래프 를 n 차 정 사각 행렬 M 으로 나 
 ‡ 1 ( 두 꼭짓점 P ‘, P Δ 가 한 개 의 변 으로 `` 연결 되 어 `` 있 을 `` 때 ) 타 낼 때 , 행렬 M 의 ( i , j ) 성분 a ‘ Δ 는 다음 과 같 다 . 
 ( 단 , i = 1 , 2 , 3 , y , n , j = 1 , 2 , 3 , y , n ) 
 ✕ a ‘ Δ = 
 0 ( 두 꼭짓점 P ‘, P Δ 가 변 으로 `` 연결 되 어 `` 있 지 `` 않 을 `` 때 ) 
 5 그래프 를 나타내 는 행렬 의 성질 ⑴ 
 한 꼭짓점 에서 자기 자신 으로 가 는 변이 없 고 , 두 꼭짓점 사이 에 많 아야 한 개 의 변이 존재 하 는 그래프 의 각 꼭짓점 사이 의 연결 관계 를 나타내 는 행렬 은 다음 과 같 은 성질 을 가지 고 있 다 . 
 ⑴ 정 사각 행렬 이 고 모든 성분 은 0 또는 1 이 다 . 
 ⑵ 행렬 의 왼쪽 위 에서 오른쪽 아래 로 향하 는 대각선 위 의 성분 은 모두 0 이 다 . 
 ⑶ 행렬 의 각 성분 은 왼쪽 위 에서 오른쪽 아래 로 향하 는 대각선 에 대하 여 대칭 이 다 . 
 ⑷ 행렬 의 각 행 ( 열 ) 의 모든 성분 의 합 은 그 행 ( 열 ) 에 해당 하 는 각 꼭짓점 에 연결 된 변의 개수 와 같 다 . 
 ⑸ 행렬 의 모든 성분 의 합 은 그래프 의 변의 개수 의 2 배 와 같 다 . 
 6 그래프 를 나타내 는 행렬 의 성질 ⑵ 
 한 꼭짓점 에서 자기 자신 으로 가 는 변이 없 고 , 두 꼭짓점 사이 에 많 아야 한 개 의 변이 존재 하 는 그래프 의 각 꼭짓점 사이 의 연결 관계 를 나타내 는 행렬 을 M 이 라 할 때 , 행 렬 M ¤ 은 다음 과 같 은 성질 을 가지 고 있 다 . 
 ⑴ 행렬 M ¤ 의 ( i , i ) 성분 은 그래프 의 제 i 행 ( 열 ) 에 해당 하 는 꼭짓점 에 연결 된 변의 개 수 와 같 다 . 
 ⑵ 행렬 M ¤ 의 ( i , j ) 성분 은 그래프 의 제 i 행 ( 열 ) 에 해당 하 는 꼭짓점 에서 출발 하 여 한 개 의 꼭짓점 을 지나 제 j 열 ( 행 ) 에 해당 하 는 꼭짓점 으로 가 는 방법 의 수 와 같 다 . 
 18 수능 완성 수학 영역 수학 Ⅰ A 형