[DiscreteMath]그래프(1)

May 5, 2023

📚기본사항

📄그래프

점과 두 점을 서로 연결하는 선으로 이루어진 도형을 그래프라고 합니다. 점을 꼭지점(Vertex) 또는 노드(Node)라고 하고, 각 점을 연결하는 선을 변(Edge)이라고 합니다.

그래프는 꼭지점의 집합과 변의 집합으로 정의됩니다. 변은 두 꼭지점을 연결하는 역할을 수행하며 변 e가 꼭지점 v와 w를 연결하는 경우 v와 w는 e에 의해 발생되었다고 하고 v와 w는 서로 인접한다고 합니다. 동일한 꼭지점을 연결하는 변은 루프라고 합니다. 두 꼭지점을 연결하는 변이 두 개 이상 있을 때 이런 변들을 병렬 변이라고 합니다. 아무 변과도 연결되지 않은 꼭지점은 고립되었다고 합니다.

꼭지점과 변의 이름을 제외하고 동일한 그래프를 동형이라고 합니다.

📄방향 그래프

변이 방향을 가지는 그래프를 방향 그래프라고 하고, 방향을 가지지 않으면 무향 그래프라고 합니다. 방향 그래프는 꼭지점 사이의 연결에 방향성이 존재할 때 사용되고 리스트나 트리와 같은 자료구조를 도식화하는데 유용합니다. 무향 그래프는 꼭지점들 사이에 전후관계가 없을 때 사용됩니다.

　　　방향 그래프　　　　　　무향 그래프
DirectedGraph UndirectedGraph
https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)

📄단순 그래프

단순 그래프는 루프나 병렬 변을 가지지 않는 무향 그래프입니다.

SimpleGraphs
https://www.tutorialspoint.com/graph_theory/types_of_graphs

📄부분 그래프

부분 그래프는 하나의 그래프가 다른 그래프에 포함되어 있는 경우를 말합니다. 그래프 H와 그래프 G가 있다고 할 때, H의 모든 꼭지점이 G의 꼭지점이고 H의 모든 변이 G의 변인 경우 H를 G의 부분 그래프라고 합니다.

📄신장 부분 그래프

신장 부분 그래프는 부분 그래프 중 특수한 성질을 만족하는 경우의 그래프를 의미합니다. 부분그래프 H의 꼭지점과 그래프 G의 꼭지점이 완전히 일치하면 H를 G의 신장 부분 그래프라고 합니다.

📄차수

차수는 그래프의 꼭지점에 대해 인접한 변의 수를 의미합니다. 그래프의 총 차수는 모든 꼭지점에 대한 차수들의 합입니다. 변이 루프일 경우 2를 더합니다.

방향 그래프에서 진입차수와 진출차수로 차수가 나뉩니다.

진입차수
방향 그래프에서 해당 꼭지점으로 들어오는 변의 수를 나타냅니다.
진출차수
해당 꼭지점에서 다른 꼭지점으로 나가는 변의 수를 나타냅니다.

📄워크, 트레일, 경로

워크
그래프 G = (V, E)에서 꼭지점 v₀와 v_k가 있다고 했을 때, v₀에서 v_k까지의 워크는 유한한 순서쌍의 형태를 가집니다.

\(W = v_{0}e_{1}v_{1}e_{2}v_{2} \; ... \; e_{k}v_{k}\)

v₀를 시작점, v_k를 종점이라고 합니다. v₁, v₂, …, v_k-1을 내부점이라고 합니다. 정수 k는 W의 길이라고 합니다. 워크 W의 시작점과 종점이 같을 경우 W는 닫혀 있다라고 합니다.

트레일
워크 W의 변들 e₁, e₂, …, e_k가 모두 서로 다르면 W는 트레일이라고 합니다.

경로
트레일 W의 꼭지점들 v₀, v₁, …, v_k가 모두 서로 다르면 W는 경로라고 합니다.

📄닫힌 트레일과 사이클

닫힌 트레일
워크 W의 변 e₁, e₂, …, e_k가 모두 서로 다르면서 v₀와 v_k가 동일한 경우 W는 닫힌 트레일이라고 합니다.

사이클
닫힌 트레일 중 v₀, v₁, …, v_k-1까지의 꼭지점이 모두 서로 다를 경우 사이클이라고 합니다.

📄연결성분과 연결 그래프

그래프에서 두 꼭지점을 서로 연결하는 경로가 있을 경우 두 꼭지점은 서로 연결되어 있다고 합니다. 꼭지점들은 서로 연결되고 다른 집합과 겹치지 않는 꼭지점의 집합으로 나눌 수 있는데, 이들 각각을 연결성분이라고 합니다. 그래프에 오직 하나의 연결성분만 있을 때 연결 그래프라고 합니다.

📚그래프의 종류

📄완전 그래프

완전 그래프는 그래프에 속한 모든 꼭지점이 다른 꼭지점과 인접할 경우를 말합니다. n개의 꼭지점을 가지는 완전 그래프는 K_n으로 표시합니다.

CompleteGraph
https://www.geeksforgeeks.org/mathematics-graph-theory-basics/

📄이분 그래프

이분 그래프는 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프입니다. 그래프 G = (V, E)의 V가 2개의 집합 V₁과 V₂로 분할되고, 모든 변들이 V₁의 꼭지점과 V₂의 꼭지점을 인접시킬 경우입니다.

https://en.wikipedia.org/wiki/Bipartite_graph

📄완전 이분 그래프

완전 이분 그래프는 꼭짓점의 집합이 서로 겹치지 않는 두 집합 X와 Y의 합집합이고 X의 모든 꼭짓점이 Y의 각각의 꼭짓점과 하나의 변으로 연결되어 있는 이분 그래프입니다. 예를 들어, 이분 그래프 G = (V, E)의 V가 V₁과 V₂로 분할되고 V₁의 모든 꼭지점과 V₂의 모든 꼭지점이 변으로 인접되어 있을 경우를 말합니다.

CompleteBipartite
https://en.wikipedia.org/wiki/Bipartite_graph