[수학과] 그래프 란?

소개글

.

목차

그래프의 정의
그래프의 표현
그래프 순회 연산

본문내용

○ 그래프의 유래- 1736년 쾨니스버그 다리 문제를  해결하기 위해서 오일러가 최초로 사용 ·두 개의 섬과 일곱 개의 다리로 구성된 지역에서  모든 다리를 정확히 한번씩 만 거쳐 다시 시작점으로 돌아올 수 있는가를 결정하는 문제 ·오일러가 불가능하다는 것을 증명 ·모든 지점과 연결된 다리의 수가 짝수여야만 가능 → 들어오는 길이 있으면 나가는 길이 있어야 가능
1 그래프의 정의○ 그래프(graph)의 정의- 그래프 G : 집합 V와 E로 구성· V : 공집합이 아닌 정점(vertex)들의 유한 집합· E : 간선(edge)들의 유한 집합- 그래프의 표기  G=(V, E)로 나타내며, G의 정점 집합은 V(G)로  간선 집합은 E(G)로 표기그래프의 분류(1) 간선들의 방향성 유무에 따른 분류 무방향 그래프(undirected graph)  ·간선에 방향이 없는 그래프 ·(v0, v1) : 정점 v0와 v1 사이의 간선  (v0, v1) = (v1, v0) 방향 그래프(directed graph, digraph)  ·간선에 방향이 부여된 그래프  ·<v0, v1> : 정점 v0와 v1 사이의 간선 <v0, v1> ≠ <v1, v0>
다중 간선이나 루프의 존재 유무에 따른 분류 단순 그래프(simple graph) ·루프(loop)나 다중 간선(multiple edge)을 갖지  않는 그래프 다중 그래프(multigraph) ·루프(loop)나 다중 간선(multiple edge)을 갖는  그래프

참고 자료

없음