ㅏ 무방향 그래프 : 간선에 방향이 없는 그래프, 즉 간선에 순회 방향을 나타내는 화살표가 없습니다. 예: 우정이 방향성이 없는 소셜 네트워크 그래프.

방향성 그래프 : 간선에 방향이 있는 그래프, 즉 간선에는 순회 방향을 나타내는 화살표가 있습니다. 예: 페이지 간의 링크가 방향성이 있는 웹 페이지 그래프.

가중치 그래프: 간선에 연관된 가중치 또는 비용이 있는 그래프입니다. 예: 가중치가 두 도시 사이의 거리를 나타낼 수 있는 도로 네트워크 그래프.

비가중 그래프 s: 간선에 가중치나 비용이 없는 그래프입니다. 예: 가장자리가 우정을 나타내는 소셜 네트워크 그래프입니다.

완전한 그래프: 각 정점이 다른 모든 정점과 연결되어 있는 그래프입니다. 예: 모든 플레이어가 다른 모든 플레이어와 대결하는 토너먼트 그래프.

이분 그래프: 모든 모서리가 한 세트의 꼭지점을 다른 세트의 꼭지점에 연결하도록 꼭지점을 두 개의 분리된 세트로 나눌 수 있는 그래프입니다. 예: 정점을 구직자와 구인으로 나눌 수 있는 구직자 그래프.

나무 : 순환이 없는 연결된 그래프입니다. 예: 각 사람이 부모와 연결되어 있는 가계도.

사이클 : 하나 이상의 주기가 있는 그래프입니다. 예: 자전거가 이동하는 경로를 자전거가 나타내는 자전거 공유 그래프.

희소 그래프: 정점의 수에 비해 상대적으로 적은 수의 간선을 갖는 그래프입니다. 예: 각 꼭지점은 화합물을 나타내고 각 모서리는 두 화합물 간의 반응을 나타내는 화학 반응 그래프입니다.

조밀한 그래프 s: 꼭지점 개수에 비해 모서리 개수가 많은 그래프. 예: 각 꼭지점은 사람을 나타내고 각 가장자리는 우정을 나타내는 소셜 네트워크 그래프입니다.

그래프 유형:

1. 유한 그래프

유한한 수의 정점과 유한한 수의 간선을 갖는 그래프를 유한하다고 합니다. 유한 그래프(finite graph)는 유한한 수의 정점과 간선을 갖는 그래프입니다. 즉, 유한 그래프의 정점 수와 간선 수는 모두 제한되어 있으며 셀 수 있습니다. 유한 그래프는 제한된 수의 개체와 개체 간의 관계가 있는 실제 상황을 모델링하는 데 자주 사용됩니다.

2. 무한 그래프:

무한한 수의 꼭지점과 변의 수를 갖는 그래프를 무한하다고 합니다.

3. 간단한 그래프:

유한 그래프에 꼭지점이 하나만 있고 간선이 없으면 그래프가 단순하다고 합니다. 간단한 그래프(Trivial Graph)는 꼭지점은 하나만 있고 간선은 없는 그래프입니다. 싱글톤 그래프(Singleton Graph) 또는 싱글 버텍스 그래프(Single Vertex Graph)라고도 합니다. 간단한 그래프는 가장 간단한 유형의 그래프이며 더 복잡한 그래프를 작성하기 위한 시작점으로 자주 사용됩니다. 그래프 이론에서 사소한 그래프는 퇴화 사례로 간주되며 일반적으로 자세히 연구되지 않습니다.

팬더와 numpy

4. 간단한 그래프:

단순 그래프는 정점 쌍 사이에 둘 이상의 간선을 포함하지 않는 그래프입니다. 여러 도시를 연결하는 간단한 철로가 간단한 그래프의 예입니다.

5. 멀티 그래프:

일부 평행 간선을 포함하지만 자체 루프를 포함하지 않는 그래프를 다중 그래프라고 합니다. 예를 들어 로드맵.

• 평행 모서리: 두 개의 정점이 둘 이상의 가장자리와 연결된 경우 이러한 가장자리를 경로는 많지만 목적지는 하나인 평행 가장자리라고 합니다.
• 고리: 정점에서 시작하여 동일한 정점에서 끝나는 그래프의 간선을 루프(loop) 또는 자가 루프(self-loop)라고 합니다.

6. 널 그래프:

차수가 n이고 크기가 0인 그래프는 정점 쌍을 연결하는 가장자리 없이 고립된 정점만 있는 그래프입니다. 널 그래프는 가장자리가 없는 그래프입니다. 즉, 정점만 있고 정점 사이의 연결은 없는 그래프입니다. 널 그래프는 경계가 없는 그래프, 고립된 그래프 또는 이산 그래프라고도 합니다.

7. 전체 그래프:

n개의 꼭지점을 갖는 간단한 그래프를 각 꼭지점의 차수가 n-1이면 완전 그래프라고 합니다. 즉, 하나의 꼭지점이 n-1개의 모서리 또는 그래프의 나머지 꼭지점과 연결되어 있는 경우입니다. 완전한 그래프를 전체 그래프라고도 합니다.

8. 의사 그래프:

자가 루프와 여러 개의 간선을 갖는 그래프 G를 의사 그래프(pseudo graph)라고 합니다. 유사 그래프는 자가 루프(정점을 자신에게 연결하는 모서리)와 다중 모서리(두 개의 꼭지점을 연결하는 둘 이상의 모서리)의 존재를 허용하는 그래프 유형입니다. 대조적으로, 단순 그래프는 루프나 다중 간선을 허용하지 않는 그래프입니다.

9. 일반 그래프:

그래프 G의 모든 정점이 동일한 차수를 갖는 경우 간단한 그래프는 정칙 그래프라고 합니다. 모든 완전한 그래프는 규칙적이지만 그 반대의 경우는 불가능합니다. 일반 그래프는 모든 정점에 동일한 수의 모서리 또는 이웃이 있는 무방향 그래프 유형입니다. 즉, 그래프가 규칙적이면 모든 정점의 차수가 동일합니다.

10. 이분 그래프:

그래프 G = (V, E)는 정점 집합 V(G)가 두 개의 비어 있지 않은 서로소 부분 집합으로 분할될 수 있는 경우 이분 그래프라고 합니다. V1(G) 및 V2(G) E(G)의 각 모서리 e는 한쪽 끝이 V1(G)이고 다른 쪽 끝이 V2(G)입니다. 파티션 V1 U V2 = V를 G의 이분이라고 합니다. 그림에서 V1(G)={V5, V4, V3} 및 V2(G)={V1, V2}

11. 라벨이 붙은 그래프:

그래프의 꼭지점과 변에 이름, 날짜, 가중치 등의 라벨이 붙어 있으면 라벨이 붙은 그래프라고 합니다. 가중치 그래프라고도 합니다.

자바 스위치 int

12. 유향 그래프:

모든 모서리가 순서가 지정된 정점 쌍(Vi, Vj)에 매핑되도록 매핑 f를 갖는 그래프 G = (V, E)를 Digraph라고 합니다. 그것은 또한 방향성 그래프 . 순서쌍(Vi, Vj)은 Vi에서 Vj를 향하는 화살표로 Vi와 Vj 사이의 간선을 의미합니다. 여기 그림에서: e1 = (V1, V2) e2 = (V2, V3) e4 = (V2, V4)

13. 하위 그래프:

그래프 G1 = (V1, E1)은 V1(G)가 V(G)의 부분 집합이고 E1(G)가 E(G)의 부분 집합인 경우 그래프 G(V, E)의 부분 그래프라고 합니다. G1의 각 모서리는 G와 동일한 끝 정점을 갖습니다.

14. 연결되거나 연결되지 않은 그래프:

그래프 G의 정점 쌍(Vi, Vj)이 서로 도달할 수 있으면 그래프 G는 연결되었다고 합니다. 또는 그래프 G의 각 꼭짓점 쌍 사이에 적어도 하나의 경로가 존재하면 그래프는 연결되어 있다고 하고, 그렇지 않으면 연결이 끊어진 것입니다. n개의 정점이 있는 널 그래프는 n개의 구성요소로 구성된 연결이 끊긴 그래프입니다. 각 구성 요소는 하나의 꼭지점으로 구성되며 가장자리는 없습니다.

15. 순환 그래프:

n개의 정점과 n> = 3인 V1, V2, V3- – – – Vn과 모서리 (V1, V2), (V2, V3), (V3, V4)- – – – (Vn, V1)을 순환 그래프라고 합니다.

16. 하위 그래프 유형:

• 정점 분리 하위 그래프: V1(G1) 교차점 V2(G2) = null인 경우 임의의 두 그래프 G1 = (V1, E1) 및 G2 = (V2, E2)는 그래프 G = (V, E)의 서로소인 정점이라고 합니다. 그림에서 G1과 G2 사이에는 공통 꼭지점이 없습니다.
• 가장자리 분리 하위 그래프: E1(G1) 교차점 E2(G2) = null인 경우 하위 그래프는 모서리 분리형(edge-disjoint)이라고 합니다. 그림에서 G1과 G2 사이에는 공통 모서리가 없습니다.

메모: 모서리 분리 하위 그래프는 공통 꼭지점을 가질 수 있지만 꼭지점 분리 하위 그래프는 공통 모서리를 가질 수 없으므로 꼭지점 분리 하위 그래프는 항상 모서리 분리 하위 그래프가 됩니다.

17. 스패닝 하위 그래프

아래와 같이 그래프 G(V,E)를 생각해 보세요. 스패닝 하위 그래프는 V'=V이고 E'가 E의 하위 집합인 경우 G'(V',E')인 원래 그래프 G의 모든 정점을 포함하는 하위 그래프입니다.

따라서 스패닝 하위 그래프 중 하나는 아래 G'(V',E')와 같을 수 있습니다. 이는 원래 그래프 G의 모든 정점과 G의 일부 가장자리를 갖습니다.

이것은 그래프 G의 많은 스패닝 하위 그래프 중 하나일 뿐입니다. 다양한 간선 조합을 통해 다양한 스패닝 하위 그래프를 만들 수 있습니다. V'=V이고 E'=E인 그래프 G'(V',E')를 고려하면 그래프 G'는 그래프 G(V,E)의 하위 그래프에 걸쳐 있습니다.

그래프의 장점:

1. 그래프는 복잡한 시스템과 관계를 모델링하고 분석하는 데 사용할 수 있습니다.
2. 데이터를 시각화하고 이해하는 데 유용합니다.
3. 그래프 알고리즘은 컴퓨터 과학 및 소셜 네트워크 분석, 물류, 운송 등 기타 분야에서 널리 사용됩니다.
4. 그래프는 소셜 네트워크, 도로 네트워크, 인터넷을 포함한 광범위한 데이터 유형을 나타내는 데 사용될 수 있습니다.

그래프의 단점:

1. 큰 그래프는 시각화하고 분석하기 어려울 수 있습니다.
2. 그래프 알고리즘은 특히 큰 그래프의 경우 계산 비용이 많이 들 수 있습니다.
3. 그래프 결과의 해석은 주관적일 수 있으며 도메인별 지식이 필요할 수 있습니다.
4. 그래프는 분석 결과의 정확성에 영향을 미칠 수 있는 노이즈 및 이상값에 취약할 수 있습니다.

관련 기사: 그래프의 응용, 장점 및 단점