8. 그래프

그래프: (V,E)쌍의 데이터 구조

• V(정점): 노드의 집합
• E(간선): 정점을 연결하는 쌍의 집합
• 정점, 간선 모두 원소, 즉, 정보를 저장한다.

EX) 공항을 표현하고 공항 도시를 정점, 공항 간의 거리를 간선이라 할 수 있다.

간선에 따른 그래프 유형

방향 간선: 간선에 방향이 존재함.

• (시점(u), 종점(v))의 순서쌍으로 표현
• 방향 그래프
  • 모든 간선이 방향 간선인 그래프

무방향 간선: 간선에 방향이 존재하지 않음.

• (정점u, 정점v)의 무순쌍으로 표현(집합으로 표현 가능)
• 무방향 그래프
  • 모든 간선이 무방향 간선인 그래프

그래프의 응용

• 전자 회로: 인쇄회로기판(PCB), 집적회로(IC)등에 사용
• 교통망:고속도로망, 항공 노선망
• 컴퓨터 네트워크: LAN, 인터넷 등
• 데이터베이스: 개체-관계 다이어그램

그래프 용어

간선의 끝점(end vertex, endpoint)

• a 간선의 양 끝점은 정점 U와 V임

정점의 부착(incident) 간선

• 정점 V의 부착간선 a,b,d가 있음

정점의 인접 정점(adjacent)

• U와 V는 서로 인접정점임.

정점의 차수(degree)

• X의 차수는 5이다.(붙어있는 간선의 개수)

병렬 간선(parallel edges)

• 같은 정점쌍에 간선 2개 이상 연결됨(h, i는 병렬간선이다.)

루프(loop, self-loop)

• 같은 정점을 연결하는 간선, (j는 루프임)

경로(path)

• 한정점에서 다른 정점으로 가는 정점, 간선의 교대열,(P1, P2등)

단순경로(simple path)

• 모든 정점과 간선이 유일한 경로(정점과 간선이 한번만 나와야함, P1)

비단순경로

• 여러번 나와도됨.(P2)

싸이클(cycle)

• 정점과 간선이 교대하는 원형열
• 시작과 끝의 정점이 같음

단순 싸이클(simple cycle)

• 모든 정점과 간선이 유일한 싸이클(C1)

비단순 싸이클

• 여러번 나와도 됨(C2)

속성

n (정점수), m(간선수), deg(v) (정점v의 차수)

1. 모든 정점의 차수를 다 더하면 간선의 2배와 같다.
   • 각 간선이 두번 세어지기 때문
   • ex) 3 + 2 + 4 + 2 + 5 + 4 = 10 * 2 = 20

1. 총 간선수는 총 정점 수(총정점수 -1)/2 보다 작거나 같다는 관계가 성립한다.(m의 상한)
   • 각 정점의 최대 차수는 (n-1)임

부 그래프(부분 집합)

그래프 G = (V,E)의 부 그래프는 V의 부분집합, E의 부분집합으로 이루어진 그래프

신장 부그래프: 정점 V와 간선 E의 부분 집합으로 이루어진 그래프(모든 정점을 취함.

연결성

모든 정점쌍에 대해 경로가 존재하면 그래프가 연결된것임.

연결요소: 연결된 정점, 간선쌍의 덩어리

• 연결 그래프: 한개의 연결요소로 이루어짐

• 비연결 그래프: 연결되지 않은 요소가 존재(n개의 연결요소로 구성)

밀집도(↔희소)

• 밀집된 그래프에서 빠른 알고리즘과 희소된 그래프에서 빠른 알고리즘이 존재한다.
• 해당 밀집과 희소의 개념은 주관적임. 개념만 알고 가자

싸이클

자유트리, 트리: 무방향 그래프가, 연결되어있으면서 싸이클이 존재하지 않는 것.

숲: 싸이클이 없는 무방향 그래프(연결 안되어있어도 됨.

신장

신장트리: 신장 부그래프 가운데 트리인것.

• 그래프가 트리일 경우 유일함, 반대는 유일하지 않음

신장숲: 신장 부그래프 가운데 숲인것.

그래프 메쏘드

일반 메쏘드

• integer numVertices(): 모든 정점 수 리턴
• integer numEdges(): 모든 간선수 리턴
• iterator vertices(): 모든 정점을 리턴
• iterator edges():모든 간선을 리턴

접근 메쏘드

• vertex aVertex(): 아무 정점을 반환함.(보통 맨앞거 리턴)

질의 메쏘드

• boolean isDirected(e): 연결그래프인지 리턴

반복 메쏘드

• iterator directedEdges(): 모든 방향 간선 리턴

갱신 메쏘드

• vertex insertVertex(o): 정점 삽입
• removeVertex(v): 정점 삭제
• removeEdge(e): 간선 삭제

무방향 그래프 메쏘드

접근메쏘드

• integer deg(v) : 정점 차수 리턴
• vertex opposite(v,e): 반대편 정점 리턴

질의 메쏘드

• boolean areAdjacent(v,w): 인접 정점인지 리턴

반복 메쏘드

• iterator endVertices(e): 양 끝점을 불러와라
• iterator adjacentVertices(v): 인접 정점을 불러와라
• iterator incidentEdges(v): 부착간선을 불러와라

갱신메쏘드

• edge insertEdge(v,w,o): 정점 v에서 w로 항목o를 저장한 무방향 간선을 삽입, 반환

방향그래프 메쏘드

접근메쏘드

• vertex origin(e): 시점 반환
• vertex destination(e): 종점 반환
• integer inDegree(v): 들어오는(진입) 간선 수 반환
• integer outDegree(v): 나가는(진출) 간선 수 반환

반복메쏘드

• iterator inIncidentEdge(v): 진입 간선 반환
• iterator outIncidentEdges(v): 진출 간선 반환
• iterator inAdjacent Vertices(v): 진입인접 정점 반환
• iterator outAdjacentVertices(v): 진출 인접 정점 반환

갱신 메쏘드

• edge insertDirectedEdge(v,w,o): 정점 v에서 w로 항목o를 저장한 방향간선 삽입 반환
• makeUndirected(e): 간선e를 무방향으로 전환
• reverseDirection(e): 방향 간선을 역행함.