정점 수, 간선 수, 상호 연결성 및 전체 구조에 따라 다양한 유형의 그래프가 있지만 이러한 일반적인 유형의 그래프는 다음과 같습니다.
1. 널 그래프
ㅏ 널 그래프 정점 사이에 간선이 없는 그래프입니다. 널 그래프는 빈 그래프라고도 합니다.
예
n개의 정점을 갖는 널 그래프는 Nn으로 표시됩니다.
2. 간단한 그래프
ㅏ 사소한 그래프 꼭짓점이 하나만 있는 그래프입니다.
예
위 그래프에는 모서리가 없는 꼭지점 'v'가 하나만 있습니다. 그러므로 이것은 사소한 그래프이다.
3. 간단한 그래프
ㅏ 간단한 그래프 방향이 없는 그래프는 다음과 같습니다. 평행한 모서리 없음 그리고 루프 없음 .
n개의 꼭지점을 갖는 간단한 그래프에서 모든 꼭지점의 차수는 최대 n -1입니다.예
위의 예에서 첫 번째 그래프는 정점 A와 B 사이에 두 개의 간선이 있고 루프도 있기 때문에 단순한 그래프가 아닙니다.
두 번째 그래프는 루프와 평행 간선을 포함하지 않기 때문에 간단한 그래프입니다.
4. 무방향 그래프
안 무방향 그래프 은 간선이 다음과 같은 그래프입니다. 감독하지 않음 .
예
위의 그래프에는 방향이 있는 간선이 없으므로 무방향 그래프입니다.
5. 방향성 그래프
ㅏ 유향 그래프 은 그래프이다. 가장자리가 방향이 지정됩니다. 화살표로.
방향성 그래프(Directed Graph)라고도 함 이중문자 .
예
위 그래프에서 각 모서리는 화살표의 방향을 따릅니다. 유향 모서리에는 A에서 B로의 화살표가 있습니다. 이는 A가 B와 관련되어 있지만 B는 A와 관련이 없음을 의미합니다.
6. 완전한 그래프
모든 정점 쌍이 정확히 하나의 간선으로 연결되는 그래프를 호출합니다. 완전한 그래프 . 가능한 모든 모서리를 포함합니다.
n개의 꼭짓점을 가진 완전한 그래프는 정확히 nC2개의 간선을 포함하며 Kn으로 표시됩니다.
예
위의 예에서 그래프의 각 정점은 정확히 하나의 간선을 통해 나머지 모든 정점과 연결되므로 두 그래프 모두 완전한 그래프입니다.
7. 연결된 그래프
ㅏ 연결된 그래프 는 임의의 한 정점에서 다른 정점으로 방문할 수 있는 그래프입니다. 연결된 그래프에서는 모든 정점 쌍 사이에 최소한 하나의 가장자리 또는 경로가 존재합니다.
예
위의 예에서는 한 정점에서 다른 정점으로 이동할 수 있습니다. 이는 모든 정점 쌍 사이에 적어도 하나의 경로가 존재하므로 연결된 그래프임을 의미합니다.
8. 연결이 끊긴 그래프
ㅏ 연결이 끊긴 그래프 모든 정점 쌍 사이에 경로가 존재하지 않는 그래프입니다.
예
위의 그래프는 연결이 끊어진 두 개의 독립적인 구성 요소로 구성됩니다. 따라서 한 구성요소의 정점에서 다른 구성요소의 정점으로 방문하는 것이 불가능하므로 연결이 끊긴 그래프입니다.
9. 정규 그래프
ㅏ 정규 그래프 모든 정점의 차수가 동일한 그래프입니다.
모든 정점의 차수를 k라고 하면 k-정규 그래프라고 합니다.
예
위의 예에서 모든 정점의 차수는 2입니다. 따라서 이를 2-라고 합니다. 정규 그래프 .
10. 순환 그래프
'n'개의 정점(n>=3)과 'n'개의 모서리가 모든 모서리와 'n'의 순환을 형성하는 그래프를 다음과 같이 알 수 있습니다. 사이클 그래프 .
최소한 하나의 사이클을 포함하는 그래프를 순환 그래프 .
순환 그래프에서 각 정점의 차수는 2입니다.
n개의 꼭지점을 갖는 순환 그래프를 Cn으로 표시합니다.
자바 널 검사
실시예 1
위의 예에서 모든 정점의 차수는 2입니다. 따라서 모두 순환 그래프입니다.
실시예 2
위의 그래프에는 두 개의 사이클이 포함되어 있으므로 순환 그래프입니다.
11. 비순환 그래프
순환을 포함하지 않는 그래프를 그래프라고 합니다. 비순환 그래프 .
예
위의 그래프에는 사이클이 포함되어 있지 않으므로 비순환 그래프입니다.
12. 이분 그래프
ㅏ 이분 그래프 정점 세트를 두 개의 세트로 분할하여 모서리가 세트 내부가 아닌 세트 사이에만 이동할 수 있는 그래프입니다.
그래프 G(V,E)는 정점 집합 V(G)가 두 개의 비어 있지 않은 서로소 하위 집합 V1(G) 및 V2(G)로 분해될 수 있는 경우 각 간선 e ∈ E인 경우 이분 그래프라고 합니다. (G)는 V1(G)에 마지막 관절이 하나 있고 V2(G)에 다른 마지막 점이 있습니다.
파티션 V = V1 ∪ V2는 G의 이중 파티션으로 알려져 있습니다.
실시예 1
실시예 2
13. 완전한 이분 그래프
ㅏ 완전한 이분 그래프 는 첫 번째 세트의 각 꼭지점이 정확히 하나의 간선으로 두 번째 세트의 각 꼭지점에 연결되는 이분 그래프입니다.
완전한 이분 그래프는 완전한 이분 그래프입니다.
Complete Bipartite graph = Bipartite graph + Complete graph
예
위의 그래프는 K로 알려져 있습니다.4,삼.
14. 별 그래프
별형 그래프는 n-1개 정점의 차수가 1이고 단일 정점의 차수가 (n -1)인 완전한 이분 그래프입니다. 이는 정확히 (n - 1)개의 정점이 단일 중앙 정점에 연결된 별처럼 보입니다.
n개의 꼭지점을 갖는 별 그래프는 S로 표시됩니다.N.
예
위의 예에서는 n개의 정점 중 (n-1)개의 정점이 모두 하나의 정점에 연결되어 있습니다. 따라서 별 그래프입니다.
15 가중치 그래프
가중치 그래프는 가장자리에 가중치나 숫자가 표시된 그래프입니다.
가중치 그래프에서 경로의 길이는 경로에 있는 모든 간선의 가중치의 합입니다.
예
위 그래프에서 경로가 a -> b -> c -> d -> e -> g이면 경로 길이는 5 + 4 + 5 + 6 + 5 = 25입니다.
16. 다중 그래프
임의의 정점 쌍 사이에 여러 개의 간선이 있거나 정점에서 자신까지의 간선(루프)이 있는 그래프를 그래프라고 합니다. 멀티 그래프 .
예
위 그래프에서 정점 집합 B와 C는 두 개의 가장자리로 연결되어 있습니다. 마찬가지로 정점 세트 E와 F는 3개의 모서리로 연결됩니다. 그러므로 다중 그래프이다.
17. 평면 그래프
ㅏ 평면 그래프 는 두 변이 서로 만나는 꼭지점을 제외하고는 서로 교차하지 않는 방식으로 평면에 그릴 수 있는 그래프입니다.
예
위 그래프는 모서리가 서로 교차하기 때문에 평면적이지 않은 것처럼 보일 수 있습니다. 하지만 위의 그래프를 다시 그릴 수 있습니다.
위 그래프의 세 가지 평면 그림은 다음과 같습니다.
위의 세 그래프는 서로 교차하는 두 개의 간선으로 구성되지 않으므로 위의 그래프는 모두 평면형입니다.
18. 비평면 그래프
평면 그래프가 아닌 그래프를 비평면 그래프라고 합니다. 즉, 적어도 한 쌍의 교차 모서리가 없으면 그릴 수 없는 그래프를 비평면 그래프라고 합니다.
예
위 그래프는 비평면 그래프입니다.