G=(V,E)는 유한한 개수의 정점(vertex) 또는 노드들의 집합인 V와 연결선(edge)이라고 불리는 정점들의 쌍들의 집합인 E로 이루어진다.
방향 그래프(directed graph, digraph)
정점 v에서 w로 가는 아크는 v -> w 로 표시한다
v를 w의 선행자predecessor라 하며w를 v의 후속자successor라 한다.
방향이 없는 그래프 undirected graph
(head -> tail)
단순 그래프 simple graph
한 쌍의 정점 사이에 많아도 하나의 연결선으로 이뤄진 통상 다루는 그래프로서 자기 자신으로의 연결선이 없는 그래프 이다.
멀티 그래프 multigraph
단순 그래프의 확장으로서 한쌍의 꼭지점사이에 연결선의 개수 제한이 없는 그래프
부분 그래프 subgraph
두개의 그래프 G=(V,E) G'=(V',E') 에서 V'⊆V, E'⊆E 일 때 G'을 G의 부분 그래프라고 한다.
서브 그래프의 정점과 간선은 원래 그래프의 부분 집합
연결선 edge
그래프에서 순서화된 쌍 E, (u,v)∈E일 때 u와 v를 연결하는 연결선 e는 u와 v에 부속됐다(incident)하고 u와 v를 서로 인접했다(adjacent)라 한다.
v의 차수 degree
d(v)는 v에 인접하는 연결선들의 개수
각 정점의 차수들의 합은 연결선 개수의 2배
방향 그래프에서는 In-Dgree, out-Dgree를 구분한다
꼭지점의 열 에서 (), 1≤k≤n 인 경우를 말하며 경로의 길이는 n-1이다.
그래프에서 간선을 따라갈 수 있는 길을 순서대로 나열한 것 에서 까지 간선으로 연결된 정점을 순서대로 나열한 리스트를 경로라 한다.
path length
경로를 구성하는 간선 수
단순 경로 simple path
경로가 같은 연결선을 두 번 포함하지 않는 경로를 말한다.
elemetary path 어떤 정점들도 두번 만나지 않는 경로를 말한다
경로 에서 종점과 시점이 일치하는 경우
단순 사이클 simple cycle
같은 연결선을 반복하여 방문하지 않는 사이클
기본 사이클 elementary cycle
시작점을 제외한 어느 정점도 반복하여 방문하지 않는 사이클
연결 그래프 connected graph
그래프의 모든 정점들이 연결된 그래프
강한 연결 그래프 strongly connected graph
모든 두 정점 a와 b에 대해서 a->b 와 b->a 경로들이 존재하는 그래프. 방향 그래프에서 의미를 가진다.
연결요소 connectivity component
그래프에서 모든 정점들이 연결되어 있는 부분을 말하며 연결수(connectivity number)란 그래프 G에서 연결 요소의 개수를 말한다.
인접행렬(adjacency matrix): 그래프 G=(V,E) 에서 |V|=n일 때 G의 인접 행렬은 n*n 행렬 A로 나타낸다. 이때 A의 각 원소 는 정점간의 연결이 있을 때 1 없으면 0
인접리스트 adjacency list
각 정점에 포인터가 주어지고 그점으로부터 연결된 정점들을 차례로 연결 리스트로 표시한 것 같은 리스트 내에서는 순서에 관계 없다.
오일러 경로(eulerian path)
그래프에서 각 연결선을 한 번씩 통과하는 경로
연결그래프이며 홀수 차수의 개수가 0또는 2여야 한다.
오일러 순회(Eulerian circuit)
그래프에서 꼭지점은 여러 번 지날 수 있지만 각 연결선은 한 번씩만 통과하는 순회
모든 정점이 짝수의 차수를 가져야 한다.
한붓그리기(traversable)
시작점과 끝점을 제외한 정점은 짝수여야 한다.
해밀턴 경로 Hamiltonian path
그래프에서 모든 꼭지점을 한번씩 지나지만 시작점으로 돌아오지 않는 경로
해밀턴 순회 Hamilton circuit
모든 꼭지점을 한 번씩 지나는 순회
가중 그래프 weight graph
그래프 G의 각 연결선에 0보다 큰 수가 할당 되었을 때 이 값을 가중값이라 한다.
동형 그래프 isomorphic graph
과 가 주어졌을 때 전단사 함수 가 존재하여 이면 f를 동형이라 하고 를 동형 그래프라 한다.
평면 그래프(planar graph)
평면상에서 어떤 연결선도 서로 교차할 수 없도록 그려진 하나의 그래프
평면 그래프의 정점 수를 v, 연결선 수를 e, 면의 수를 f라 할때
v-e+f=2 이때 f는 그래프 바깥의 평면도 포함한다.
완전 그래프 complete graph
G=(V,E)의 모든 정점들의 쌍 사이에 연결선이 존재.
Kn (n은 정점 수)
정규 그래프 regular graph
그래프의 모든 꼭지점의 차수가 k일 때 k차 정규 그래프라고 한다.
이분 그래프 bipartite graph
G가 두 부분집합 X,Y= V-X 로 나누어져 연결선이 X내의 정점과 Y내의 정점의 쌍으로 연결되면 G를 이분 그래프라고 한다.
완전 이분 그래프 complete bipartite graph
X내의 정점들과 Y내의 정점들 사이에 연결선이 모두 존재하는 그래프
방향 비사이클 그래프 DAG Directed Acyclic Graph
사이클이 없는 방향 그래프이다.
공통 인수를 가진 산술적 표현의 구조를 나타내는 데 유용하다.
coloring problem
G에 대해 인접한 영역이 서로 다른 색이 되도록 각 저점에 색을 칠하는 문제
chromatic number
G를 칠하는데 필요한 최소의 색의 수 x(G)
쌍대 그래프
두 그래프가 동형이 될 때
그래프 G에서 다음은 서로 동치
두가지 색으로 칠할 수 있다.
이분 그래프이다.
모든 순환은 짝수의 길이를 가진다.
four coloring problem
모든 평면글래프는 네 가지 색으로 색칠 가능하다.
최단경로 문제, 다익스트라, 순회 판매원(최근접 이웃 근삿값), DFS, BFS 자료구조랑 겹쳐서 나중에 어디에 넣을지 고민
모든 정점이 n개인 무방향 그래프 G에서 정점이 n개이고 간선이 n-1개인 트리 형태의 부분 그래프.
간선을 최소로 하여 모든 정점을 방문한다.
그래프에서 순회를 하면 n-1개의 간선을 이동하면서 n개의 모든 정점을 방문하게 되므로 순회경로는 신장 트리가 된다.
Depth First Spanning Tree: 깊이 우선 탐색을 이용하여 생성된 신장 트리
Breadth First Spanning Tree: 너비 우선 탐색을 이용하여 생성된 신장 트리
Minimum cost spanning tree: 가중치 합이 최소인 신장 트리
주어진 가중 그래프 G=(V,E)에서 V={1,2, ... , n}
신장 트리가 아닌 가중치 그래프, 즉 네트워크에서 정점 u와 정점 v를 연결하는 경로 중에서 가중치의 합이 최소인 경로.
최단 경로를 구하려는 가중치 그래프의 가중치는 ‘가중치 인접 행렬(Weight Adjacent Matrix)’에 저장한다. 2차원 배여. 두 정점 사이 간선이 없으면 , 대각선 값0