그래프(이산수학)

이산수학 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.1.1. 그래프

2.1.1.1. 방향그래프2.1.1.2. 다중그래프2.1.1.3. 유향 다중그래프2.1.1.4. 가중 그래프

2.1.2. 기본 개념

2.1.2.1. 이웃2.1.2.2. 차수2.1.2.3. 입력차수와 출력차수

2.2. 구조 및 분류

2.2.1. 완전 그래프2.2.2. 보행, 사이클, 경로2.2.3. 연결 그래프2.2.4. 트리2.2.5. n분 그래프

2.2.5.1. 이분 그래프

2.2.6. 매칭

2.3. 성질

2.3.1. 동형

2.3.1.1. 동형

2.3.2. 연결의 정도2.3.3. 평면성

3. 관련 문제 및 알고리즘

1. 개요

그래프는 그래프 이론에서 다루는 수학적 대상이다. 그래프는 정점(또는 꼭짓점)과, 두 정점을 연결하는 변(또는 모서리)들로 구성된다. 일반적으로 정점은 점으로 표현하고 변은 선분으로 표현한다. 변에 방향을 부여한 그래프를 유향 그래프(Directed graph)라고 하며, 이 경우 변을 화살표로 표현한다. 다음의 그림은 그래프를 도식화한 예시이다.

예를 들어 도시를 정점으로 생각하고 도시 사이를 잇는 도로를 변으로 생각하면 그래프는 곧 하나의 간략화된 지도가 된다. 위의 그림에서 1~6번 원이 도시고 연결선이 도로인 셈. 이렇게 그래프는 도시를 정점으로, 도로를 변으로 보는 것처럼 나타낼 수 있기 때문에 두 지점 간의 최단 경로(또는 가장 저렴한 경로)를 구하는 등의 문제에서 널리 이용된다. 그래프는 도시-도로뿐만 아니라 컴퓨터 통신망, SNS에서의 친구관계 등등 여러 상황을 모델링 할 수 있어 많은 분야에서 널리 사용된다. 예를 들어 어떤 웹 페이지를 정점으로 하고 페이지에 달린 링크들을 다른 페이지로 가는 변이라고 보면, 나무위키 역시 하나의 거대한 그래프라고 볼 수 있다.

그림의 그래프에서는 2,3,4,5번 정점들이 서로 연결되어 하나의 순환을 이룬다. 다시 말해서 2번 정점에서 출발하여 3,4,5번 정점을 순서대로 하나씩만 거친 후 다시 2번에 도착할 수 있는데, 이러한 구조를 순환 또는 사이클이라고 한다. 한편 이렇게 순환을 가지지 않는 연결된 그래프를 트리(그래프)라고 한다.

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

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

2. 용어와 개념

2.1. 정의

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

2.1.1. 그래프

그래프(graph) [math(G)]는 정점(vertex)[2]의 집합 [math(V=V(G))][3]와 변(edge)[4]의 집합 [math(E=E(G))]의 순서쌍 [math(\displaystyle G=(V, E) )]으로 정의된다. 여기서 변의 원소 [math(e \in E)]는 두 개의 정점으로 구성된 집합이다. 예를 들어 두 정점 [math(u,v)]를 잇는 변은 [math(e = \{ u, v \})]로 정의되며, [math(uv)]로 표기한다. 이 때 [math(u,v)]를 [math(e)]의 끝점(endpoint)이라 하고, [math(u)]와 [math(v)]는 서로 이웃한다(adjacent)고 하며 [math(u)]를 [math(v)]의 이웃(neighbor)이라고 한다. 그리고 '[math(e)]는 [math(u)](또는 [math(v)])와 붙어있다(incident)'고 표현하고 '[math(e)]가 [math(u,v)]를 연결한다(connect)'고 말한다.

[math(V)]가 유한인 그래프를 유한 그래프(finite graph)라고 하며, 유한이 아닌 그래프를 무한 그래프(infinite graph)라고 한다. 일반적으로 별도의 서술이 없이 그래프라 하면 유한 그래프를 의미한다.

일반적으로 그림에서 정점은 점이나 원으로 표현되고, 변은 두 꼭짓점을 잇는 선으로 표현된다. 예를 들어, 첫 문단 그림의 그래프를 [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} )]

2.1.1.1. 방향그래프

그래프의 정의에서, [math(e \in E)]를 집합이 아닌 순서쌍 [math(\displaystyle e \equiv (u,v))]와 같이 정의한 그래프를 방향그래프(directed graph, digraph)라고 한다. 이때 [math(e)]는 방향변(방향모서리, directed edge 또는 arc)이라고 한다. 이때, [math(u)]는 [math(e)]의 시점, [math(v)]는 [math(e)]의 종점이라 하며, '[math(e)]는 [math(u)]에서 시작하여 [math(v)]에서 끝난다', 또는 '[math(u)]에서 [math(v)]로 간다'와 같이 표현한다. 흔히 그림에서 유향변은 시점에서 종점으로 향하는 화살표로 표현된다.

한편, 유향그래프가 아닌 그래프를 무방향그래프(비방향성 그래프, undirected graph)라 한다. 일반적으로 그래프라고 하면 무방향그래프를 의미한다.

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

2.1.1.2. 다중그래프

다중그래프(multigraph)는 두 꼭짓점을 연결하는 여러 개의 변이나, 정점에서 출발해 자기 자신으로 돌아오는 루프를 허용하는 그래프이다. 즉 다중그래프는 서로소인 정점 집합 [math(V)]과 변 집합 [math(E)]의 순서쌍 [math((V,E))]와 함께 다음의 함수 [math(\partial)]을 가지는 집합이다.

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

여기서 공역은 [math(S^2(V) = \left\{ \left\{ u, v \right\}|u, v \in V \right\})]으로, [math(V\cup\binom{V}{2})]와 같다. 즉, [math(\partial)]은 각각의 변마다 두 끝점 또는 하나의 정점을 정해주는 함수이다.

이전의 정의와는 달리, [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)] 이외에도 여러 개가 있을 수 있는데, 이 경우 두 정점은 여러 변과 연결되어 있다고 할 수 있는 것이다.

하나의 정점에서 출발해 자기 자신으로 돌아오는 변을 루프(loop), 또는 고리라 한다. 즉 루프는 다중 그래프에서 [math(\partial)]의 값이 하나의 원소로 정해지는 변이다.

다중그래프가 아닌 그래프를 단순 그래프(simple graph)라 하며, 문맥에 따라 다르지만 일반적으로 그래프라 하면 단순 그래프를 의미한다.

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

2.1.1.3. 유향 다중그래프

다중 그래프에도 변의 방향을 적용하는 방법을 생각할 수 있다. 그러나 다중 그래프에서는 변의 두 끝점을 [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.1.1.4. 가중 그래프

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

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

2.1.2. 기본 개념

2.1.2.1. 이웃

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

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

정점의 집합 [math(A)]에 대해서, [math(A)]의 이웃 [math(N(A))]는 모든 [math(v \in A)]의 이웃의 합집합 [math(\displaystyle N(A)=\bigcup_{v \in A}N(v))]이다.

2.1.2.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| )]

2.1.2.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.2. 구조 및 분류

그래프 [math(G)]의 부분그래프 [math(H)]는 [math(V(H) \subset V(G))]이고 [math(E(H) \subset E(G))]인 그래프로 정의한다. [math(V(H)=V(G))]인 경우 [math(H)]를 [math(G)]의 생성그래프(spanning subgraph)라고 한다.

그래프 [math(G)]의 정점의 부분집합 [math(U\subset G)]에 대하여, [math(U)]의 정점들을 연결하는 [math(G)]의 모든 변들로 생성되는 그래프를 유도된 부분그래프(induced subgraph)라고 하며 [math(G[U])]로 표기한다. 즉, [math(G[U])]는 정점 집합 [math(U)]와 변 집합 [math(\{e\in E(G):e\subset U\})]를 가지는 그래프이다.

그래프 [math(G)]의 여 그래프(complement graph) [math(\bar{G})]는 [math(G)]의 이어지지 않은 모든 변들을 변으로 가지는 그래프이다. 즉 [math(\bar{G}=(V,\binom{V}{2}\setminus E))]이다.[5]

2.2.1. 완전 그래프

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

2.2.2. 보행, 사이클, 경로

서로 인접한 변들의 나열을 보행(walk)이라고 한다. 즉 보행 [math(v_1v_2\cdots v_n)]은 정점 [math(v_i)]와 변 [math(v_iv_{i+1}\in E(G))]들의 나열이다. 이때 변의 수 [math(n-1)]를 보행의 길이(length)라고 한다. 보행은 같은 정점 또는 같은 변을 여러 번 거칠 수 있다. 보행의 시작점과 끝점이 같으면 닫혀있다(closed)고 한다.
중복된 변을 가지지 않는 보행을 트레일(trail)이라고 하며, 닫힌 트레일을 회로(circuit)이라고 한다.

모든 정점이 다른 보행을 경로(path)라고 한다. 즉 경로는 같은 정점을 다시 거치지 않는 변들의 나열이다. 길이가 [math(n)]인 경로를 일반적으로 [math(P_n)]으로 표기한다.

끝점을 제외한 모든 정점이 다른 회로를 사이클(cycle)이라고 한다. 즉 사이클은 같은 정점을 다시 거치지 않으면서 시작점과 끝점이 같은 변들의 나열이다. 길이가 [math(n)]인 사이클을 일반적으로 [math(C_n)]으로 표기한다.

2.2.3. 연결 그래프

임의의 두 정점을 변들로 연결할 수 있는 그래프를 연결 그래프(connected graph)라고 한다. 즉 연결 그래프는 임의의 두 정점 [math(u,v\in V(G))]에 대해 [math(u)]에서 [math(v)]로 가는 경로가 존재하는 그래프이다. 주어진 그래프의 연결 부분 그래프가 더 이상 정점이나 변을 추가하면 연결 그래프가 아니게 될 때 이 부분 그래프를 그래프의 성분(component) 또는 연결 성분이라고 부른다. 즉, 그래프의 성분은 포함 관계에 대해 극대인 연결 그래프이다.

2.2.4. 트리

사이클을 부분 그래프로 가지지 않는 그래프를 비순환 그래프(acyclic graph) 또는 포레스트(forest)라고 한다.

비순환 연결 그래프를 트리(tree) 또는 나무라고 한다. 트리는 다음 방식들로 정의할 수도 있으며, 모두 동치인 조건들이다.
(1) 임의의 두 정점들 사이에 경로가 유일하게 존재한다.
(2) 임의의 변을 추가했을 때 사이클이 생긴다.

2.2.5. n분 그래프

정점 집합이 서로소인 n개의 부분집합들로 분할될 수 있는 그래프를 n분 그래프(n-partite graph)라고 한다.

2.2.5.1. 이분 그래프

서로소인 두 정점 부분집합 [math(X)], [math(Y)]들 사이를 연결하는 변만을 변으로 가지는 그래프를 이분 그래프(bipartite graph)라 한다. [math(X,Y)]-이분 그래프라고도 한다. 즉 이분 그래프는 n분 그래프에서 n=2인 경우이다.
이분 그래프의 판별법은 두 가지 색으로 모든 점들을 색칠하는 건데, 인접한 점들은 다른 색만 사용하는 것이다. 만약 색칠을 하다 인접한 점끼리 반드시 같은 색으로 칠해야만 하는 상황이 온다면 해당 그래프는 이분 그래프가 아니다. 조금 더 간편한 방법으로는 이분 그래프 내부에 cycle이 짝수 개의 edge를 가지고 있으면 이는 이분 그래프가 되기 위한 필요충분조건이 된다. 표기법은 [math(|V_1|=m, |V_2|=n)]이라 했을 때 [math(K_{m,n})]. 이를 보다 확장시켜서 [math(n)]분 그래프라는걸 생각할 수 있는데, 표기법은 마찬가지로 각 정점 집합의 분할의 위수를 아래첨자로 나열한다.

2.2.6. 매칭

매칭(matching)이란 서로 연결되지 않은 변들의 집합을 뜻한다. 한 그래프에서 얻을 수 있는 매칭 중 제일 원소의 개수가 많은 매칭을 최대 매칭이라 하며, 모든 정점들을 포함하는 매칭을 완전 매칭(perfect matching)이라 한다.

홀의 정리(Hall's theorem)는 그래프 [math(G)]가 완전 매칭을 가질 필요충분조건에 대한 정리이다. 이 정리에 의하면, [math(X,Y)]-이분 그래프 [math(G)]가 완전 매칭을 가질 필요충분조건은 [math(X)]의 모든 부분집합 [math(A)]에 대해서 [math(N(A))]의 크기가 [math(A)]의 크기 이상인 것이다.

2.3. 성질

2.3.1. 동형

우선 그래프를 어떤 식으로 표현할 수 있을지를 생각해보자. 단순하게 각 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.3.1.1. 동형

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

2.3.2. 연결의 정도

그렇다면 연결된 그래프의 연결이 어느정도로 강한지를 정의할 수 있는 방법은 무엇일까. 이는 얼마나 많은 점 또는 모서리를 제거해야 연결이 사라지는지로 나타낼 수 있다. 이러한 점들의 집합을 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.3.3. 평면성

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

[math(G)]가 연결 단순 그래프이고, 그래프의 차수[6]가 [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})]의 부분분할[7]을 포함하는 그래프를 내포하지 않는다는 것이 알려져 있다.

3. 관련 문제 및 알고리즘

[1] 모든 정점들을 한 번씩만 지나는 경로[2] 또는 꼭짓점. 공학계열에서는 '노드(node)'라고 부르기도 한다.[3] 보통 따로 명시되지 않는 이상 [math(V \neq \varnothing)]이다.[4] 또는 모서리[5] [math(\binom{V}{2})]는 [math(V)]의 서로 다른 원소 2개로 구성된 모든 집합들을 원소로 가지는 집합족이다.[6] 해당 그래프의 모든 닫힌 도형의 변의 수를 합한 것. 평면 그래프라면 변의 수의 2배가 된다. 이는 평면그래프는 구면상에서 정의되기 때문으로, 그래프 외부 역시 도형으로 취급하기 때문.[7] 주어진 그래프의 선 위에 임의로 점을 찍은 것을 생각할 수도 있는데, 이런 그래프를 주어진 그래프의 부분분할, 혹은 세분이라고 표현한다.