정의

1. vertex(node)와 edge(간선)으로 이루어진 것
2. 표현
   1. V(g) = {a, b, c, d, e}
   2. E(g) = {(a,b), (a,c), (a,d), (b,e), (d,e)}

용어

1. adjacent: 두 vertex간의 edge 존재
2. path: 두 vertex간에 edge로 연결된 vertex의 sequence
3. length of a path: path를 구성하는 edge 개수
4. connected: 두 vertex간에 path가 존재
5. connected component: 연결된 요소
6. cycle: 시작과 끝이 동일 vertex인 path
7. degree of vertex: 그 vertex와 연결된 edge 수(그래프의 방향성 여부에 따라 용어 의미가 조금씩 달라짐)
   1. indegree: incoming edge(directed graph만 존재)
   2. outdegree: outgoing edge
8. fully connected graph의 edge 수
   1. n(n-1)/2

edge

1. (V1, v2): 방향성이 없는 edge --> graph(undirected graph)
2. <v1, v2>: 방향성을 갖는 edge --> directed graph(digraph)
   1. strongly connected: directed graph에서 양방향 path 존재(edge가 아니라 path임)
3. 한 그래프에 두개의 edge가 있는 경우는 없음

한붓 그리기

1. 선을 떼지 않고 한번에 그릴 수 있는 도형
2. 한붓 그리기 가능한 graph 형태
   1. degree가 홀수인 vertex가 없거나 2개인 경우
      1. degree가 홀수이면 시작점이나 마지막 지점이 되어야 하기때문에

그래프 표현

1. matrix
   1. undirected graph: 대칭(가운데 대각선 기준)
2. 링크드 리스트
   1. matrix와 달리 실제 vertex들에 대한 정보만 저장

그래프 탐색(search)

1. dfs(깊이 우선 탐색)
   1. 백트래킹을 위해 스택 필요 --> 스택 empty일 때 종료
2. bfs(너비 우선 탐색)
   1. 큐 사용

spanning tree

1. graph g의 spanning tree
   1. g의 모든 vertex를 연결하는 cycle이 없는 subgraph
2. 그래프의 최소 연결 그래프, 모든 vertex를 연결하면서 cycle이 존재 하지 않는 최소 연결 그래프

biconnected components

1. articulation point를 갖지 않는 connected graph --> 양쪽으로 튼튼하게 연결이 되어 있음을 의미
2. articulaion point(단절점)
   1. 해당 vertex를 삭제 했을 때, 원 그래프가 두 개 이상의 biconnected component로 분리되는 vertex

minimum cost spanning tree

1. weighted graph에서 cost의 합이 최소인 spanning tree를 찾는 문제 --> 여러개의 spanning tree 중에서 cost의 합이 최소인 spanning tree를 찾는 문제
2. krukal's algorithm
   1. 전체 edge의 집합을, cost 순서로 sorting
   2. cost 순서로, 해당 edge가 cycle을 이루지 않으면 선택
   3. (n-1)개의 edge가 선택될 때까지 반복
3. prim's algorithm --> krukal 같은 경우는 어디서 edge가 생성될 지 모르기 때문에 더 복잡하다고 생각
   1. connected component와 외부로 연결된 edge중에서 최소 cost edge 선택
   2. (n-1)개의 edge가 선택될 때까지 반복
4. solin's algorithm
   1. 각 vertex를 서로 다른 connected component로 고려
   2. 각 connected component에 대하여 최소 cost edge를 한 개씩 추가 --> spanning tree를 찾는 문제이므로 cycle이 되는 경우는 고려하지 않음, cycle을 이루지 않는 경우 선택
   3. 전체가 한 개의 connected component가 되면 종료

shortest path algorithm

1. 특정 vertex에서 다른 모든 vertex에 이르는 최단 거리 path를 구하는 문제
2. 기준 vertex에 해당하는 row를 초기값으로 설정
3. 다음을 (n-2)회 반복 --> 맨 처음 노드는 처음 vertex 선택하는 것으로 대체, 가장 마지막 노드는 나머지가 다 처리되어 할 작업이 없음
   1. 아직 방문하지 않은 vertex 중에서 가장 가까운 vertex 선택
   2. 해당 vertex를 거쳐서 가는 path가 현재 알려진 path보다 짧으면 수정

matrix 표현

1. adjacancy matrix: A
   1. vertex간 edge가 존재하면 1, 아니면 0
2. transitive closure(이행적 폐쇄 행렬): A+
   1. vertex간에 path가 존재하면 1, 아니면 0
   2. 가운데 대각선 1 --> cycle 존재
3. reflexive transitive closure: A*
   1. 자신과의 path도 고려한 transitive closure

activity network

1. aov(activity on vertex) networks
   1. directed graph
   2. vertex: 어떤 task나 activity를 의미
   3. edge: activity의 선후관계를 의미
   4. 예시: topological sort --> 모든 vertex가 선택되지 않은 경우: cycle이 존재하는 경우
2. aoe(activity on edge) networks
   1. edge가 activity를 의미하며, vertex는 시작과 종료 event 의미
   2. critical path(유사: bottle neck)
      1. 전체 성능에 영향을 주는 activities
      2. start vertex부터 finish vertex까지의 longest path
   3. earliest start time --> 빠르면 언제부터 시작할 수 있는지
      1. 해당 activity가 시작될 수 있는 가장 빠른 시간
   4. latest start time --> 늦어도 언제는 시작해야 함
      1. 해당 activity가 시작되어야 하는 가장 늦은 시간