항목
-
그래프 graph나타내는 사상 Φ : E → V×V의 조 G=(V, E, Φ)를 그래프라 한다. Φ를 생략하고 G=(V, E)라 기술하는 수도 있다. 가지에 방향을 생각하지 않을 때 G를 무향 그래프(undirected graph) (그림 a), 가지에 방향을 생각할 때 유향 그래프(directed graph)라 부른다(그림 b). 노드는 정점(vertex), 점(point) 등으로도...
- 분야 :
- 수학
-
행렬표현(그래프의) matrix representation (of graph)그래프 G를 행렬로 표현한 것을 G의 행렬표현이라고 한다. G=(V,E)를 무향 그래프로 하여, V={vi│1≦i≦n}, E={ei│1≦i≦m}으로 한다. n×n행렬 A=(aij)로, vi과 vj를 연결하는 가지수가 k일 때 aij=k로 한 것을 G의 인접행렬(adjacency matrix)이라고 한다. 그림 1의 그래프의 인접행렬을 그림 2에 표시한다. n×m...
- 분야 :
- 수학, 프로그래밍
-
2부 그래프 bipartite graph2부 그래프라고 한다. G는 G=(V1, V2, E) 라고도 쓸 수 있다. 그림 (a)의 그래프는 그림 (b)와 같이 V를 둘로 분할할 수 있기 때문에 2부 그래프이다. 무향 그래프 G가 2부 그래프가 되기 위한 필요충분 조건은 G가 홀수 길이의 단순 폐로(경로 참고)를 포함하지 말아야 한다. 또는 G의 채색수가 2 이하일 경우라 해도...
- 분야 :
- 수학
-
리스트 표현(그래프의) list representation(of graph)더 나아가서 노드나 가지의 삽입이나 삭제가 동적으로 실행되게 하려는 응용에는, 위의 가지의 집합을 쌍방향 리스트로 표현하면 편리하다. 또한 무향 그래프는 각 가지가 2개의 유향 가지라 보고 유향 그래프로서 표현하면 좋다(예를 들면 2개의 가지는 본래의 가지 번호를 2배하여 0이나 1을 보탬으로써 표현한다...
- 분야 :
- 수학, 프로그래밍
-
그래프 알고리즘 graph algorithms데는 여러 가지 검색의 방법을 생각할 수 있는데, 특히 깊이 우선검색과 폭 우선검색이 흔히 쓰인다. 이 계통적인 검색을 기초로 하는 산법으로, 무향 그래프를 2연결성분(연결성 참고)으로 분해하는 것, 그래프가 평면 그래프인가 아닌가를 판정하는 것(평면 그래프의 판정 참고)을 비롯하여, 수많은 문제를 고속으로...
- 분야 :
- 프로그래밍
-
평면 그래프의 판정 planarity testing무향 그래프를 입력으로 하여, 그것이 평면 그래프인지 아닌지를 판정하는 것. 이 문제에 대해서는 실용적인 고속산법이 알려져 있다. 호프크로프트-타잔(Hopcroft, J. E. - Tarjan, R. E., 1974)의 산법은, 아우슬랜더-파터(Auslander, L. - Parter, S. V., 1961) 등의 산법을 근본으로 하여 깊이우선 검색을 이용한 것...
- 분야 :
- 수학, 프로그래밍
-
독립집합(그래프의) 안정집합, independent set(of graph)G=(V, E)의 노드의 집합 S(⫅V)에서, S의 어느 2 노드도 인접해 있지 않을 때, S를 G의 독립집합이라 한다. 안정집합(stable set)이라고도 한다. S가 단순무향 그래프 G의 독립집합이라는 것과, G의 보그래프 GC에서 S가 크리크라는 것과는 동등이다. 일반적으로 그래프 G의 최대독립집합을 구하는 문제는 NP곤란이다.
- 분야 :
- 수학
-
완전 그래프 complete graph임의의 다른 2노드에 대해, 그것들을 양 끝점으로 하는 가지가 존재하는 것과 같은 단수무향 그래프. n개의 노드를 가지는 완전 그래프를 Kn으로 적는다. Kn은 n(n-1)/2개의 가지를 가진다. 〈참조어〉 그래프, 크리크, 정칙 그래프
- 분야 :
- 수학
-
정규 그래프 정칙 그래프, regular graph정칙 그래프라고도 한다. 모든 노드의 차수가 같은 무향 그래프. 노드의 차수가 r일 때, 정규 그래프의 차수는 r이 라고 한다 n개의 노드를 가지는 완전 그래프 Kn은 차수 n-1의 정규 그래프이다. 〈참조어〉 그래프
- 분야 :
- 수학
-
무향 가지 non-directional branch네트워크의 정보 전송 용량을 계산하기 위하여 네트워크를 그래프로 추상화하는데 이때 통신로가 가지에 해당한다. 가지 중에서 전이중(full-duplex) 채널이나 반이중(half-duplex) 채널과 같이 양방향적으로 신호가 흐르는 채널을 나타내는 것을 무향 가지라고 한다.
- 분야 :
- 정보통신
