이산 수학 8장 그래프

그래프의 개념
그래프 : 정점과 변으로 구성된 집합
인접 : 정점과 정점
근접 : 정점과 정점을 이어주는 변
단순 그래프 : 두 정점 사이에오직 하나의 변이 있는 그래프
다중 그래프 : 두개 이상
방향 그래프 : 방향이 있다.
가중치 그래프 : 가중치가 있다
차수 : 정점 v에 근접하는 변의 개수
외차수 : 정점 v를 시작으로 하는 화살표 개수
내차수 : 정점 v를 끝점으로 하는 화살표의 개수
차수가 홀수인 정점의 개수는 짝수이고, 모든 정점의 차수의 합은 변의 개수의 2배이다.

그래프의 종류
부분 그래프 : 일부분의 정점과 변을 포함한 그래프
신장 부분 그래프 : 모든 정점을 포함하는 부분 그래프 
동형 그래프 : 그래프에서 정점의 위치만 조금씩 바꾸고 나머지는 그대로 인 것
연결 그래프 : 정점 u,v 사이에 경로가 있는 그래프
경로 : u,v 사이에 가는 길 중에서 같은 변을 두 번 이상 포함하지 않는 길
평면 그래프 : 정점이 아닌 위치에서는 어떤변도 교차하지 않도록 그린 그래프
오일러 공식 : 정점 수 - 변의 수 + 영역 수 = 2
정규 그래프 : 모든 정점의 차수가 k로 같은 그래프
완전 그래프 : 모든 정점 사이에 변이 존재하는 그래프
이분 그래프 : 정점을 두 그룹으로 나눠서 같은 그룹 끼리는 왕래가 없고 다른 그룹끼리 연결된 것
완전 이분 그래프 : 이분 그래프 중에서 다른 그룹끼리 철저하게 다 와싿 갔다 하는 것.

그래프의 표현
인접 행렬
인접 리스트

오일러와 해밀턴
순환 / 회로 : 연결 그래프에서 시작하는 정점과 끝나는 정점이 같은 경로
길이 : 변의 수
오일러 경로 : 모든 변을 한번씩만 지나는 경로
차수가 홀수인 정점의 수가 0개 또는 2개이다.
오일러 순환 : 임의의 정점 v에서 시작하여 모든 변을 한 번씩만 지나 다시 정점 v로 돌아오는 경로 
모든 정점의 차수가 짝수인 것
오일러 그래프 : 오일러 순환을 가지는 그래프
해밀턴 경로 : 모든 정점을 한 번씩만 지나는 경로
해밀턴 순환 : v에서 시작하여 모든 정점을 한 번씩 지나 정점 v로 다시 돌아오는 경로

그래프의 활용
최단 경로 문제

2023.12.10 - [알고리즘/공부] - 최단경로 개념

최단경로 개념

다익스트라 알고리즘
DFS 
BFS