이산 수학 8장 그래프 개념 정리
vertices = 점
edges = 선
weighted graph = edge에 대해 넘버링 되어 있는 것, 번호 붙어 있으면 weighted
directed graph = 화살표
path와 length of path 구분
길 개수 vs 길의 전체 길이
connected = 모든 점이 연결되어 있을 때, 동 떨어져있는 점이 없을 때
subgraph = 어떤 그래프에서 떼어 만들진 새로운 그래프
component = 그래프 덩어리 개수(?) ex) one component, 2 component
simple path = 두 번 지나지 않는 것
cycle(or circuit) = v에서 v로 돌아오는 것(+nonzero)
simple cycle = 각각의 점을 한 번만 지나면서 처음 한 점으로 돌아오는 것
ex) cycle of length를 구하시오 : 선 개수 세서 쓰면 됨
euler cycle = 모든 선을 한 번씩만 지나서 자기 자신에게 돌아오는 것
degree of a vertex = 한 점에서 뻗어갈 수 있는 길의 수
euler graphs = vertex가 모두 짝수이어야 함(필요 충분 조건-> vertex 모두 짝수 = euler graph임)
hamiltonian cycles = 모든 점을 한 번씩 지나며 처음 출발한 곳으로 되돌아 오는 것(선이 아니라 점!->euler와의 차이점)
isomorphic = 그래프 간단화, 대응점/대응선
planar = 크로스 안 되게 그래프 그리기
face = 영역
edges in series = 그래프 단순화, 필요 없는 점 생략
series reduction = 최소의 vertex만 사용(=간단화)
homeomorphic = 간단히 했을 때 똑같이 생긴 그래프의 관계, 동상
parallel computation models = 그래프 병렬
말로 설명하기 어려워서 그림 가져옴
각 점 앞에 0, 1 붙이기 -> 뒷자리는 똑같고, 맨 앞만 다른 점끼리 연결 ex) 00-10, 01-11 // 010-110, 011-111, 000-100 등