자료구조 | Graphs | 숙명여대 학점교류

학점교류로 듣는 숙명여대 자료구조

day 12. 2022.1.6. 목요일

---

Koenigsberg Bridge problem

다리를 한번씩만 건너서 처음 위치에 돌아올 수 있을까? 

=> 오일러 경로

중복없이 원래 자리로 돌아올 수가 없다. 

 

그래프로 문제를 풀고자 했던 첫번째 시도

edge, node로 표현했다. 

Euler's principle - vertex의 차수가 짝수여야지 풀 수 있다. 

 

Graphs

G = (V, E)

V is a vertex set = nodes, points

E is an edge set

 

type : undirected graph / directed graph (digraph)

undirected graph : no oriented edge

directed graph : has orient

 

Undirected Graph

- disconnected 되어있어도 괜찮다

 

Directed graph

applications - communication network

vertex = city, edge = communication link

driving distance / time weight : edge weight = cost(distance or time)

street map : some streets are one way

 

complete undirected graph

완전 무방형 그래프

complete if a graph has all possible edges

assumption : no self-edge, double edge

 

number of edges - undirected graph

each edge is of the form (u, v), where u!=v

number of such pairs in n-vertex graph is n(n-1)

since edge (u, v) is the same as edge (v, u), the number of edges in complete undirected graph is n(n-1)/2

number of edges in undirected graphs is <= n(n-1)/2

 

number of edges - directed graph

each edge is of the form <u, v>, where u!=v

number of such pairs in n-vertex graph is n(n-1)

since edge <u, v> is not the same as edge <v, u>, the number of edges in complete undirected graph is n(n-1)/

number of edges in undirected graphs is <= n(n-1)

 

vertex degree

연결된 간선의 수

 

sum of vertex degrees

sum of degrees = 2e, where e is number of edges

 

in-degree of a vertex

방향성 있는 것

두 종류로 나누어서 계산한다. 

in-degree, out-degree

indegree : 정점진입차수 number of inbound edges

2 = 1, 8 = 0, 7 =2

outdegree : 진출차수? 

outdegree(2) = 1, outdegree(8) = 2

 

sum of In- and out- degrees

sum of in-degrees = sum of out-degrees = e

* e = number of edges in the digraph

 

Graph Problems

path finding problem

connected ness problem

minimum cost spanning tree problem

 

connected Graph

if there is a path between every pair of vertices

=> connected components

연결되어있는 sub 부분을 components라고 한다. 

 

maximal subgraph that is connected

cannot add vertices and edges from original graph

 

전체를 포괄하고 있어야 한다. 

 

communication network problems

만약에 통신 장애가 발생하면, components를 찾기도 한다. 

흥미롭군

 

cycles and connectedness

removal of an edge that is on a cycle does not affect connectedness

 

tree 정의

What is the Difference Between Tree and Graph - Pediaa.Com

a connected graph that has no cycle

n vertex connected graph with n-1 edges

 

그래프에서 중복된 것을 제외하고 그린 것을

spanning tree라고 한다. 

 

spanning tree

a subgraph that includes all vertices of the original graph and should be a tree

if original graph has n vertices

 

minimum cost spanning tree

최소 비용 신장 트리

tree cost is sum of edge weight tree