그래프(이산수학)

이산수학 Discrete Mathematics
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all"	이론
<colbgcolor=#3CC> 기본 대상	수학기초론( 수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 확률
다루는 대상과 주요 토픽
수열	등차수열( 뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의( 점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수
조합	경우의 수( /공식) · 순열( 완전 순열 · 염주 순열) · 치환 · 분할( 분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론
그래프	수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기( 해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제
기타	P-NP 문제^미해결 · 4색정리 · 이항정리( 파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설^미해결 · 콜라츠 추측^미해결 · 시행착오 ( 예상과 확인) · 불 논리 · 브라에스 역설
관련 문서	논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학	}}}}}}}}}

[[컴퓨터공학|컴퓨터 과학 & 공학

Computer Science & Engineering

]]

[ 펼치기 · 접기 ]

||<tablebgcolor=#fff,#1c1d1f><tablecolor=#373a3c,#ddd><colbgcolor=#0066DC><colcolor=white> 기반 학문 || 수학( 해석학 · 이산수학 · 수리논리학 · 선형대수학 · 미적분학 · 미분방정식 · 대수학( 환론 · 범주론) · 정수론) · 이론 컴퓨터 과학 · 암호학 · 전자공학 · 언어학( 형태론 · 통사론 · 의미론 · 화용론 · 음운론) · 인지과학 ||

하드웨어 구성	SoC · CPU · GPU( 그래픽 카드 · GPGPU) · ROM · RAM · SSD · HDD · 참조: 틀:컴퓨터 부품
기술	기계어 · 어셈블리어 · C/ C++ · C# · Java · Python · BIOS · 절차적 프로그래밍 · 객체 지향 프로그래밍 · 해킹 · ROT13 · 일회용 비밀번호 · 사물인터넷 · 와이파이 · GPS · 임베디드 · 인공신경망 · OpenGL · EXIF · 마이크로아키텍처 · ACPI · UEFI · NERF · gRPC · 리버스 엔지니어링 · HCI · UI · UX · 대역폭 · DBMS · NoSQL · 해시( SHA · 브루트 포스 · 레인보우 테이블 · salt · 암호화폐) · RSA 암호화 · 하드웨어 가속
연구 및 기타	논리 회로( 보수기 · 가산기 · 논리 연산 · 불 대수 · 플립플롭) · 정보이론 · 임베디드 시스템 · 운영 체제 · 데이터베이스 · 프로그래밍 언어{ 컴파일러( 어셈블러 · JIT) · 인터프리터 · 유형 이론 · 파싱 · 링커 · 난해한 프로그래밍 언어} · 메타데이터 · 기계학습 · 빅데이터 · 폰노이만 구조 · 양자컴퓨터 · 행위자 모델 · 인코딩( 유니코드 · MBCS) · 네트워크 · 컴퓨터 보안 · OCR · 슈퍼컴퓨터 · 튜링 머신 · FPGA · 딥러닝 · 컴퓨터 구조론 · 컴퓨터 비전 · 컴퓨터 그래픽스 · 인공지능 · 시간 복잡도( 최적화) · 소프트웨어 개발 방법론 · 디자인 패턴 · 정보처리이론 · 재귀 이론 · 자연어 처리( 기계 번역 · 음성인식) · 버전 ( 버전 관리 시스템 · Git · GitHub)

''' 이론 컴퓨터 과학 {{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"'''
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px"	<colbgcolor=#a36> 이론
기본 대상	수학기초론{ 수리논리학( 논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학( 그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학
다루는 대상과 주요 토픽
계산 가능성 이론	재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버
오토마타 이론	FSM · 푸시다운 · 튜링 머신( 폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어
계산 복잡도 이론	점근 표기법 · 튜링 기계^^{고전, 양자, 비결정론적, 병렬 임의접근 기계}^ · 알고리즘 · 자료구조 · 알고리즘 패러다임( 그리디 알고리즘, 동적 계획법)
정보이론	데이터 압축( 무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학
프로그래밍 언어이론	프로그래밍 언어( 함수형 언어 · 객체 지향 프로그래밍 · 증명보조기) · 메타 프로그래밍 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론
주요 알고리즘 및 자료구조
기초	정렬 알고리즘 · 순서도 · 탐색 알고리즘
추상적 자료형 및 구현	배열^^벡터^ · 리스트^^{연결 리스트}^ · 셋(set)^^{레드-블랙 트리, B-트리}^ · 우선순위 큐^^{힙, 피보나치 힙}^
수학적 최적화	조합 최적화	외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습
	볼록 최적화	내부점 방법 · 경사하강법
	선형계획법	심플렉스법
계산 수론 및 암호학	밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시( MD5 · 암호화폐 · 사전 공격( 레인보우 테이블) · SHA) · 양자 암호
	대칭키 암호화 방식	블록 암호 알고리즘( AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4)
	공개키 암호화 방식	공개키 암호 알고리즘( 타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9)
계산기하학	볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^^{Fortune의 line-sweeping 알고리즘}^ · 범위 탐색^^{vp-tree, R-tree}^ · k-NN
그래프 이론	탐색^^{BFS, DFS, 다익스트라 알고리즘, A* 알고리즘}^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론
정리
정지 문제^{대각선 논법} · 암달의 법칙 · P-NP 문제^미해결 · 콜라츠 추측^미해결
틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학			}}}}}}}}}

1. 개요2. 용어와 정의

2.1. 그래프의 성질2.2. 그래프의 정의와 변형

2.2.1. 그래프2.2.2. 방향그래프2.2.3. 다중그래프

2.2.3.1. 유향 다중그래프

2.2.4. 가중 그래프2.2.5. 그래프의 변형

2.3. 특수한 그래프

2.3.1. 완전 그래프2.3.2. 사이클2.3.3. 휠2.3.4. 기타 그래프의 분류

2.4. 정점과 관련된 용어

2.4.1. 이웃2.4.2. 차수2.4.3. 입력차수와 출력차수

2.5. 그래프의 매칭

2.5.1. 매칭의 성질

2.6. 그래프의 동형

2.6.1. 동형

2.7. 길, 경로, 그래프의 연결성

2.7.1. 연결의 정도

2.8. 평면성

3. 관련 문제 및 알고리즘

1. 개요

그래프는 정점(Vertex)과 정점들을 연결하는 변(Edge)으로 구성이 된다. 일반적으로 정점은 원으로 표현하고 변은 화살표나 선분으로 표현한다. 변을 화살표로 나타내는 경우에는 해당 방향으로만 이동할 수 있으며, 이러한 그래프를 유향 그래프(Directed graph)라고 말한다. 반대로 선분으로 표현되는 경우에는 양방향 모두 이동이 가능하며, 이러한 그래프를 무향 그래프(Undirected graph)라고 말한다. 그리고 변의 경우에는 특정한 수치를 가질 수 있는데 이를 가중치(Weighted value)라고 말한다.

예를 들어 도시를 정점으로 생각하고 도시 사이를 잇는 도로를 변으로 생각하면 그래프는 곧 하나의 간략화된 지도가 된다. 위의 그림에서 1~6번 원이 도시고 연결선이 도로인 셈. 여기에 각 도로마다 도로의 길이 또는 이용 요금을 써 넣으면 이것이 바로 그 도로의 가중치이다.

위에서 알 수 있듯이 그래프는 도시와 도로로도 비유될 수 있기 때문에 두 지점 간의 최단 경로(또는 가장 저렴한 경로)를 구하는 데 널리 이용된다. 그래프는 도시-도로뿐만 아니라 컴퓨터 통신망, SNS에서의 친구관계 등등 여러 상황을 모델링 할 수 있어 많은 분야에서 널리 사용된다. 예를 들어 어떤 웹 페이지를 정점으로 하고 페이지에 달린 링크들을 다른 페이지로 가는 변이라고 보면, 나무위키 역시 하나의 거대한 그래프라고 볼 수 있다.

위의 그림에서는 2,3,4,5번 도시(정점)들이 서로 연결되어 순환할 수 있다. 다시 말해서 2번 도시에서 출발하여 3,4,5번 도시를 거쳐 다시 2번에 도착할 수 있다는 것. 이와는 반대로, 이렇게 순환하지 않는 그래프를 트리(그래프)라고도 부른다.

순수수학에서는 수학자 레온하르트 오일러가 한붓그리기 문제, 즉 쾨니히스베르크 다리 건너기 문제를 푼 것을 그래프 이론의 시작으로 보고 있다. 이 외에도 그래프 이론에서 대중에게 비교적 친숙한 문제로는 4색정리나 해밀턴 회로 [1] 등이 있을 것이다.

과거 2007 개정 교육과정까지 고등학교 수학에 등장했던 '행렬과 그래프'라는 단원에서의 그래프는 해석학적인 그래프가 아니라 바로 이 그래프를 뜻한다.

2. 용어와 정의

그래프는 일반적으로 위 그림과 같이 점과 선분을 이용한 그림으로써 표현되는 경우가 많다. 그러나 그래프 이론 또한 수학의 한 분야인 이상, 이를 이용하여 정리를 세우거나, 각종 문제를 풀기 위해서는 우선 그래프와 그에 관련된 개념을 수학적으로 엄밀하게 정리할 필요가 있다. 그래프와 관련된 용어는 집합과 함수 등을 이용하여 정의될 수 있다.

예를 들어, 위 그림의 그래프를 [math(G = (V, E))]라 했을 때 꼭짓점의 집합 [math(V)]와 변의 집합 [math(E)]를 엄밀하게 정의하면 다음과 같다.

[math(\displaystyle \begin{aligned} &V = \{1, 2, 3, 4, 5, 6\} \\ &E = \left\{ \{1, 2\}, \{1, 5\}, \{2, 3\}, \{2, 5\}, \{3, 4\}, \{4, 5\}, \{4, 6\} \right\} \end{aligned} )]

그래프 이론이 비교적 최근에 생긴 이론인 만큼 시간대나 활용하는 분야에 따라 같은 정의라도 용어가 다르거나, 심지어 정의 자체가 다른 경우도 있다. 그러므로 상황에 따라 용어를 유동적으로 해석할 수 있어야 하며, 정의를 분명하게 명시해야만 한다. 예를 들어 '꼭짓점(vertex)'은 컴퓨터공학을 비롯한 공학계열에서는 ' 노드(node)'라는 이름으로 불리기도 한다. 사정이 이렇다 보니 이를 번역한 교재에 따라 한국어 번역이 중구난방이다.

2.1. 그래프의 성질

악수정리가 대표적인 성질인데, 어떤 그래프의 차수는 항상 존재하는 모든 edge의 2배이다. 이를 통해 홀수개의 차수를 갖고 있는 vertice의 수는 항상 짝수라는 점을 유도할 수 있다.

2.2. 그래프의 정의와 변형

그래프는 그래프 이론에서 다루는 수학적 대상이다. 그래프 이론의 초기에는 그래프가 한 종류였지만, 현대에 들어 컴퓨터공학, 전자공학 등의 발전으로 인해 여러 변형이 생겼다.

2.2.1. 그래프

그래프(graph) [math(G)]는 꼭짓점의 집합 [math(V)][2]와 변의 집합 [math(E)]의 순서쌍으로 정의된다. 즉,

[math(\displaystyle G \equiv (V, E) )]

당연하게도 [math(V)]의 원소는 꼭짓점(vertex), [math(E)]의 원소는 변(모서리, edge)라 부른다. 흔히 그림에서 꼭짓점은 점이나 원으로 표현되고, 변은 두 끝점을 잇는 선분으로 표현된다.

변의 집합 [math(E)]는 모든 [math(e \in E)]가 [math(v_1, v_2 \in V)]에 대해

[math(\displaystyle e = \{ v_1, v_2 \})]

가 되도록 정의한다. 이 때 [math(v_1, v_2)]를 [math(e)]의 끝점(endpoint)이라 하고, [math(v_1)]과 [math(v_2)]는 서로 인접한다(adjacent) 또는 이웃한다(neighbor)고 한다. '[math(e)]는 [math(v_1, v_2)]와 붙어있다(incident)' 또는 '[math(v_1, v_2)]를 연결한다(connect)'고 한다. 두 꼭짓점 [math(v_1)], [math(v_2)]를 연결하는 변을 간단히 [math(v_{1}v_{2})]와 같이 표기하기도 한다.

2.2.2. 방향그래프

그래프의 정의 중 [math(e \in E)]에 대한 정의를 다음과 같이 바꾸어 준 것을 방향그래프(directed graph, digraph)라고 한다.

[math(\displaystyle e \equiv (v_{1}, v_{2}) )]

보다시피, 순서를 나타내기 위해 집합이 아닌 순서쌍을 이용하였다. 여기서 [math(e)]는 방향변(방향모서리, directed edge 또는 arc)이라고 한다. 이때, [math(v_1)]은 [math(e)]의 시점, [math(v_2)]은 [math(e)]의 종점이라 하며, '[math(e)]는 [math(v_1)]에서 시작하여 [math(v_2)]에서 끝난다', 또는 '[math(v_1)]에서 [math(v_2)]로 간다'와 같이 표현한다. 흔히 그림에서 유향변은 시점에서 종점으로 향하는 화살표로 표현된다.

한편, 유향그래프가 아닌 그래프를 무방향그래프(비방향성 그래프, undirected graph)라 한다.

유향그래프는 무향그래프와 달리 두 정점 사이의 단방향적인 관계를 표현할 수 있다.

2.2.3. 다중그래프

다중그래프(multigraph)는 두 꼭짓점을 연결하는 변이 여러 개인 그래프이다. 엄밀하게는, 그래프의 정의를 다음과 같이 변형한 것을 다중그래프라고 한다.

[math(\displaystyle G \equiv (V, E, \partial) )]

여기서 [math(\partial : E \to S^2(V))]는 함수이고, 공역 [math(S^2(V) = \left\{ \left\{ u, v \right\}|u, v \in V \right\})]이다. 즉, [math(S^2(A))]는 [math(A)]의 부분집합들 중 원소가 2개인 것만 원소로 하는 집합족이다.

이전의 정의와는 달리, [math(E)]의 원소, 즉 변은 끝점을 이용하여 정의되지 않는다. 그 대신 어떤 변이 어떤 두 끝점과 연결되는지를 함수 [math(\partial)]로 정의하는 것이다. 예를 들어 [math(\partial e_1 = \{u, v\})]라면 변 [math(e_1)]의 끝점은 [math(u)]와 [math(v)]라는 뜻이다. [math(\partial e = \{u, v\})]가 되는 변 [math(e)]는 [math(e_1)] 이외에도 여러 개가 있을 수 있는데, 이 경우 두 꼭짓점은 여러 변과 연결되어 있다고 할 수 있는 것이다.

다중그래프가 아닌 그래프를 단순 그래프(simple graph)라 한다.

다중그래프는 단순그래프와 달리 두 정점 사이의 여러 관계를 표현할 수 있다.

2.2.3.1. 유향 다중그래프

다중 그래프에도 변의 방향을 적용하는 방법을 생각할 수 있다. 그러나 다중 그래프에서는 변의 두 끝점을 [math(E)]의 정의가 아닌 새로운 함수 [math(\partial)]를 이용해 결정했으므로, 유향 다중그래프(directed multigraph)는 다음과 같이 [math(\partial)]의 공역을 고쳐 새롭게 정의해야 한다.

[math(\displaystyle \partial : E \to V^2)]

여기서 [math(V^2 = V \times V = \left\{ \left( u, v \right)|u, v \in V \right\})]이다. 즉, 유향 그래프와 마찬가지로 두 꼭짓점들의 집합을 순서쌍으로 바꾼 것이다.

2.2.4. 가중 그래프

가중 그래프(weighted graph)는 각각의 변에 가중치(weight)라 불리는 값을 대응한 그래프이다. 엄밀하게는 가중치 함수 [math(W : E \to \mathbb{R})]를 추가한 그래프로 정의할 수 있다.

가중치는 그래프 모델이 쓰이는 상황에 따라 다르게 정의되어 다양하게 활용될 수 있다. 예를 들어 비행기의 항로를 그래프로 모델링한다면, 운항 거리, 시간, 항공비 등을 가중치로 고려할 수 있는데, 최단 경로 문제의 풀이법을 이용하면 '목적지까지 가장 빨리, 비용이 적게 도착할 수 있는 항공편은?' 같은 질문에 답할 수 있게 된다.

2.2.5. 그래프의 변형

Induced Subgraph 어떤 vertice를 제거하며 그와 연결된 모든 모서리도 같이 제거하여 얻는 일종의 subgraph
모서리 제거와 추가 말 그대로의 정의
contraction 어떤 vertice를 다른 vertice로 겹쳐지면서 생기는 변형. 만약 e를 f로 contract하는데 e와 f가 동시에 연결된 모서리가 있다면 그 모서리는 하나로 합쳐지게 된다.
그래프의 합집합 말 그대로 두 그래프를 그대로 합치는 변형이다. 위치상 겹치는 점과 모서리들은 전부 하나로 합쳐진다.

2.3. 특수한 그래프

2.3.1. 완전 그래프

Complete graph
모든 서로 다른 꼭짓점끼리 연결되는 그래프를 말한다. 이때 꼭짓점이 [math(n)]개인 그래프를 n-완전 그래프(n-complete graph)라 하며, [math(K_n)]로 쓴다.
꼭짓점의 개수가 [math(n)]개일 때, 변의 개수는 [math(n(n-1) \over 2)]개이며, 모든 꼭짓점의 차수는 [math(n-1)]라는 성질이 있다.
완전 그래프가 아닌 그래프, 즉, 최소 한 쌍의 서로 연결되지 않은 꼭짓점 쌍이 존재하는 그래프를 불완전 그래프(incomplete graph)라 한다.

2.3.2. 사이클

[math(i)]번째 꼭짓점을 [math(v_i)]라고 할 때, 사이클(cycle, 순환 또는 회로) [math(C_n)]은 꼭짓점의 개수가 [math(n)]개이며,

[math(\displaystyle E = \left\{ v_{1}v_{2}, v_{2}v_{3}, v_{3}v_{4}, \cdots, v_{n-1}v_{n}, v_{n}v_{1} \right\} )]

인 그래프이다.

어느 부분그래프(subgraph)도 사이클이 아니며[3], 모두 연결된 그래프를 트리(tree)라고 한다.

2.3.3. 휠

[math(i)]번째 꼭짓점을 [math(v_i)]라고 할 때, 휠(wheel) [math(W_n)]은 꼭짓점의 개수가 [math(n+1)]개이며,

[math(\displaystyle E = \left\{ v_{1}v_{2}, v_{2}v_{3}, v_{3}v_{4}, \cdots, v_{n-1}v_{n}, v_{n}v_{1}, \quad v_{1}v_{n+1}, v_{2}v_{n+1}, v_{3}v_{n+1}, \cdots, v_{n-1}v_{n+1}, v_{n}v_{n+1} \right\} )]

인 그래프이다.
사이클 [math(C_n)]에 새로운 꼭짓점 [math(v_{n+1})]을 추가하고, [math(C_n)]에 있던 꼭짓점들과 [math(v_{n+1})]을 서로 연결함으로써 만들 수 있다.

2.3.4. 기타 그래프의 분류

무한 그래프(infinite graph): [math(V)]가 무한집합인 그래프. 즉, 꼭짓점의 개수가 무한한 그래프를 말한다. 무한 그래프가 아닌 그래프는 유한 그래프(finite graph)다.
이분 그래프: 어떤 그래프의 모든 점집합을 두개의 V1, V2로 분리했을 때 모든 모서리가 V1,V2 사이에만 있고 V1,V2 내부에는 없는 그래프를 이분그래프라고 한다. 판별법은 두가지 색으로 모든 점들을 색칠하는 건데, 인접한 점들은 다른 색만 사용하는 것이다. 만약 색칠을 하다 인접한 점끼리 반드시 같은 색으로 칠해야만 하는 상황이 온다면 해당 그래프는 이분그래프가 아니다. 조금 더 간편한 방법으로는 이분그래프 내부에 cycle이 짝수개의 edge를 가지고 있으면 이는 이분그래프가 되기 위한 필요충분조건이 된다. 표기법은 [math(|V_1|=m, |V_2|=n)]이라 했을 때 [math(K_{m,n})]. 이를 보다 확장시켜서 [math(n)]분 그래프라는걸 생각할 수 있는데, 표기법은 마찬가지로 각 점집합의 분할의 위수를 아래첨자로 나열한다.
하이퍼그래프(hypergraph): 간선이 임의의 갯수의 정점을 연결하는 그래프를 의미한다. [math(\forall e \in E, \exists i \in \mathbb{Z}, 0 \ge i \ge |V|, e = \{v_1, ... , v_i \})]

2.4. 정점과 관련된 용어

2.4.1. 이웃

꼭짓점 [math(v)]에 대해서, [math(v)]의 이웃(neighborhood) 또는 인접(adjacent)은 [math(v)]와 이웃한(neighbor) 꼭짓점들의 집합이며, 기호로는 [math(N(v))]와 같이 쓴다. 예를 들어 단순 무향 그래프인 경우에는 다음과 같다.

[math(\displaystyle N(v) = \left\{u \in V | \left\{u, v \right\} \in E \right\})]

꼭짓점의 집합 [math(A)]에 대해서, [math(A)]의 이웃은 모든 [math(v \in A)]의 이웃의 합집합이다. 즉 다음과 같다.

[math(\displaystyle N(A) \equiv \bigcup_{v \in A}N(v))]

2.4.2. 차수

무향 그래프의 꼭짓점 [math(v)]의 차수(degree)는 기호로 [math(\operatorname{deg}(v))] 또는 [math(d(v))]라 쓰며, 다음과 같이 정의된다.

[math(\displaystyle \operatorname{deg}(v) \equiv \left| N(v) \right| + 2\left|\left\{ \{v\} \in E \right\}\right| )]

즉, 모든 [math(v)]와 연결된 모서리에 대해 다음의 과정을 통해 정의될 수 있다.

[math(\operatorname{deg}(v))]를 [math(v)]와 연결된 고리(loop)가 아닌 모서리의 개수로 정한다.
[math(v)]와 연결된 고리의 개수당 2를 더한다.

차수는 꼭짓점에 연결된 모서리의 수를 나타내는데, 고리에 대해 2를 더하는 것은 고리를 포함하는 그래프에서 일반적인 성질을 유지하기 위한 장치이다.

2.4.3. 입력차수와 출력차수

유향 그래프의 꼭짓점 [math(v)]의 입력차수(in-degree) [math(\operatorname{deg}^{-}(v))]와 출력차수(out-degree) [math(\operatorname{deg}^{+}(v))]는 다음과 같이 정의된다.

[math(\displaystyle \begin{aligned} \operatorname{deg}^{-}(v) \equiv& \left|\left\{ u \in V | (u, v) \in E \right\}\right| \\ \operatorname{deg}^{+}(v) \equiv& \left|\left\{ u \in V | (v, u) \in E \right\}\right| \end{aligned} )]

즉, 입력차수와 출력차수는 [math(v)]를 종점과 시점으로 갖는 모서리의 수이다. 단, 고리(loop)는 입, 출력차수 모두에 1씩 영향을 미친다.

2.5. 그래프의 매칭

매칭이란 서로 연결되지 않은 모든 모서리들의 집합을 뜻한다. 최대매칭은 한 그래프에서 얻을 수 있는 매칭중 제일 원소의 개수가 많은 매칭을 뜻하고, 완전매칭이란 모든 vertice들을 포함하는 매칭을 의미한다.

2.5.1. 매칭의 성질

Hall's Theorem 이분인 점 (V1,V2)를 갖는 이분그래프 G=(V,E)가 V1에서 V2로 완전매칭일 필요충분조건은 V1의 모든 부분집합 A에 대해서 A의 원소의 cardinality보다 V2에 있는 A의 이웃집합 N(A)의 cardinality가 크거나 같아야 한다.

2.6. 그래프의 동형

우선 그래프를 어떤 식으로 표현할 수 있을지를 생각해보자. 단순하게 각 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의 선형대수 교재에서도 사용되는 방식으로, 이를 통해 여러 대상들 사이의 에너지 교환을 행렬로 표현하여 전체 시스템의 변화를 기술하는데에 응용될수도 있다.

보다 자세한 내용은 인접행렬 문서 참조.

2.6.1. 동형

동형을 isomorphism이라고 부르는데, 이는 두 그래프 G1=(V1,E1)과 G2=(V2,E2)가 있을 때 V1으로부터 V2의 일대일대응이 존재하고, 그 대응에 의해서 E1이 E2로 대응되는 경우 두 그래프를 isomorphism이라고 정의한다.

2.7. 길, 경로, 그래프의 연결성

각 모서리들을 많아야 한번 지나는 것을 길(trail), 각 점들을 많아야 한번 지나는 것을 경로(path)라고 하며, 시작점과 끝점이 같은 경로를 closed path 또는 닫힌 경로라고 한다. 또한 모든 점들이 경로로 연결된 그래프를 연결된 그래프라고 부른다.

2.7.1. 연결의 정도

그렇다면 연결된 그래프의 연결이 어느정도로 강한지를 정의할 수 있는 방법은 무엇일까. 이는 얼마나 많은 점 또는 모서리를 제거해야 연결이 사라지는지로 나타낼 수 있다. 이러한 점들의 집합을 separating set이라고 부르며, cut vertex는 오로지 하나의 vertex만을 지니는 separating set을 뜻한다. 이때 연결그래프 [math(G)]의 연결성을 [math(\kappa \left(G\right))]라고 하는데 이는 separating set의 cardinality의 최솟값을 의미한다. 만약 [math(\kappa \left(G\right) \ge k)]면 G을 [math(k)]-connected하다고 부른다. 즉 점을 하나만 제거해도 연결성이 제거된다면 1-connected, 2개를 제거해야 한다면 2-connected라고 하는 것.

이는 당연히 모서리를 통해서도 정의가 가능한데, 모서리의 경우에는 disconnecting set이라 하며, cutset은 disconnecting set의 극소이며, bridge는 하나의 모서리를 가진 cutset을 뜻한다. 여기서 극소라 하면, 어떤 그래프에서 몇몇 모서리만을 지정하고, 이 모서리중에서 그래프를 분리시킬 수 있는 최소의 모서리들을 뜻하기 때문에, 전체 그래프에 해당되는 개념이 아니다. 여기서는 연결성을 [math(\lambda \left(G \right))]라고 하며, [math(\lambda \left(G \right) \ge k)]면 [math(G)]를 [math(k)]-edge-connected이라고 정의한다.

2.8. 평면성

그래프의 모든 변이 평면상에서 서로 교차하지 않는 위상동형 그래프를 그릴 수 있을 때, 평면성을 가진다고 한다.
해당 그래프 [math(G)]가 어떤 그래프냐에 따라서 평면성을 판정하는 방법이 달라진다.

[math(G)]가 연결 단순 그래프이고, 그래프의 차수[4]가 [math(d\left(G\right)\geq 3)]일 때
[math(G)]가 평면 그래프 [math(\displaystyle \Rightarrow v\geq 2+\frac{e}{3})]
[math(G)]가 연결 이분 단순 그래프이고, 그래프의 차수가 [math(d\left(G\right)\geq 3)]일 때
[math(G)]가 평면 그래프 [math(\displaystyle \Rightarrow v\geq 2+\frac{e}{2})]
[math(G)]가 연결 단순 그래프라면
[math(G)]가 평면 그래프 [math(\displaystyle \Rightarrow \forall e_i \in E, d\left(e_i\right)\leq 5)]

또한 쿠라토프스키 정리(Kuratowski's Theorem)에 의해서, 평면 그래프는 [math(K_5)]와 [math(K_{3,3})]의 부분분할[5]을 포함하는 그래프를 내포하지 않는다는 것이 알려져 있다.

3. 관련 문제 및 알고리즘

[1] 모든 정점들을 한 번씩만 지나는 경로 [2] 보통 따로 명시되지 않는 이상 [math(V \neq \varnothing)]이다. [3] 즉, 내부에 사이클이 없으며 [4] 해당 그래프의 모든 닫힌 도형의 변의 수를 합한 것. 평면 그래프라면 변의 수의 2배가 된다. 이는 평면그래프는 구면상에서 정의되기 때문으로, 그래프 외부 역시 도형으로 취급하기 때문. [5] 주어진 그래프의 선 위에 임의로 점을 찍은 것을 생각할 수도 있는데, 이런 그래프를 주어진 그래프의 부분분할, 혹은 세분이라고 표현한다.