정점의 내차수와 외차수를 이해하려면 먼저 정점의 차수 개념을 알아야 합니다. 그러면 정점의 내차수와 외차수를 쉽게 이해할 수 있습니다. 안쪽 차수와 바깥 차수는 방향성 그래프에서만 결정될 수 있다는 것을 알아야 합니다. 무방향 그래프를 사용하여 정점의 각도를 계산할 수 있습니다. 무방향 그래프에서는 꼭지점의 안쪽 차수와 바깥쪽 차수를 계산할 수 없습니다.
꼭지점의 정도
그래프에서 각 꼭지점의 차수를 찾으려면, 이 경우 특정 꼭지점이 다른 꼭지점과 맺은 관계의 수를 세어야 합니다. 즉, 해당 정점에 연결된 모서리 수를 계산하여 정점의 정도를 결정할 수 있습니다. 정점의 각도는 deg(v)를 사용하여 표시됩니다. n개의 정점을 포함하는 간단한 그래프가 있는 경우 이 경우 정점의 차수는 다음과 같습니다.
Deg(v) = n-1 ∀ v ∈ G
정점은 자신을 제외한 그래프의 다른 모든 정점과 간선을 형성할 수 있는 능력이 있습니다. 그래서 간단한 그래프에서 꼭지점의 차수는 그래프에 있는 꼭지점의 개수에서 1을 뺀 값으로 알 수 있습니다. 여기서 1은 자체적으로 루프를 만들지 않기 때문에 자체 꼭지점으로 사용됩니다. 그래프에 자체 루프가 있는 정점이 포함되어 있으면 해당 그래프 유형은 단순한 그래프가 아닙니다.
예:
이 예에는 a, b, c, d, e, f라는 6개의 꼭지점을 갖는 그래프가 있습니다. 정점 'a'의 차수는 5이고 다른 모든 정점의 차수는 1입니다. 정점에 차수가 1인 경우 해당 정점 유형을 '끝 정점'이라고 합니다.
정점의 정도를 고려할 수 있는 그래프에는 두 가지 경우가 있는데, 이를 설명하면 다음과 같습니다.
- 무방향 그래프
- 유향 그래프
이제 유방향 그래프의 꼭지점 정도와 무방향 그래프의 꼭지점 정도에 대해 자세히 알아보겠습니다.
무방향 그래프의 정점 정도
무방향 그래프가 있는 경우 이 유형의 그래프에는 방향이 있는 간선이 없습니다. 무방향 그래프에서 꼭지점의 정도를 결정하는 예는 다음과 같습니다.
예시 1: 이번 예제에서는 방향이 없는 그래프를 살펴보겠습니다. 이제 해당 그래프의 각 꼭지점의 정도를 알아 보겠습니다.
해결책: 위의 무방향 그래프에는 a, b, c, d, e 총 5개의 정점이 있습니다. 각 정점의 차수는 다음과 같습니다.
- 위 그래프에는 꼭지점 'a'에서 만나는 2개의 간선이 포함되어 있습니다. 따라서 Deg(a) = 2
- 이 그래프에는 꼭지점 'b'에서 만나는 3개의 간선이 포함되어 있습니다. 따라서 Deg(b) = 3
- 위 그래프에는 꼭지점 'c'에서 만나는 1개의 간선이 포함되어 있습니다. 따라서 Deg(c) = 1입니다. 꼭지점 c는 늘어진 꼭지점으로도 알려져 있습니다.
- 위 그래프에는 꼭지점 'd'에서 만나는 2개의 간선이 포함되어 있습니다. 따라서 Deg(d) = 2입니다.
- 위 그래프에는 꼭지점 'e'에서 만나는 0개의 모서리가 포함되어 있습니다. 따라서 Deg(a) = 0입니다. 정점 e는 고립된 정점이라고도 할 수 있습니다.
예시 2: 이번 예제에서는 방향이 없는 그래프를 살펴보겠습니다. 이제 해당 그래프의 각 꼭지점의 정도를 알아 보겠습니다.
해결책: 위의 무방향 그래프에는 a, b, c, d, e 총 5개의 정점이 있습니다. 각 정점의 차수는 다음과 같습니다.
정점 a의 각도 = deg(a) = 2
정점 b의 각도 = deg(b) = 2
정점 c의 각도 = deg(c) = 2
배열 목록 정렬
꼭지점의 각도 d = deg(d) = 2
정점 e의 각도 = deg(e) = 0
이 그래프에는 늘어진 꼭지점이 없으며, 꼭지점 'e'는 고립된 꼭지점입니다.
유방향 그래프의 정점 정도
그래프가 방향성 그래프인 경우 이 그래프에서 각 꼭지점에는 진입 차수와 진출 차수가 있어야 합니다. 방향성 그래프가 있다고 가정해보자. 이 그래프에서는 다음 단계를 사용하여 꼭지점의 내차수, 외차수 및 차수를 알아낼 수 있습니다.
정점의 차수
꼭지점의 내부 차수는 v가 있는 모서리의 수로 설명할 수 있습니다. 여기서 v는 끝 꼭지점을 나타내는 데 사용됩니다. 즉, 정점에 도달하는 수많은 모서리로 설명할 수 있습니다. 구문 deg의 도움으로-(v), 정점의 차수를 쓸 수 있습니다. 꼭지점의 내부 차수를 결정하려면 꼭지점에서 끝나는 가장자리의 수를 계산해야 합니다.
꼭지점의 이탈 차수
꼭지점의 아웃 차수는 v가 있는 모서리의 개수로 설명할 수 있습니다. 여기서 v는 초기 꼭지점을 나타내는 데 사용됩니다. 즉, 정점에서 나오는 여러 개의 모서리로 설명할 수 있습니다. 구문 deg의 도움으로+(v), 정점의 진출 차수를 쓸 수 있습니다. 정점의 아웃 차수를 결정하려면 정점에서 시작하는 가장자리의 수를 계산해야 합니다.
꼭지점의 정도
정점의 차수는 정점의 내부 차수와 정점의 외부 차수를 더한 것과 동일한 deg(v)의 도움으로 표시됩니다. 정점 각도의 기호 표현은 다음과 같이 설명됩니다.
Deg(v) = deg-(v) + deg+(v)
예시 1: 이 예에는 그래프가 있으며 각 꼭지점의 차수를 결정해야 합니다.
해결책: 이를 위해 먼저 정점의 차수, 정점의 내부 차수, 정점의 외부 차수를 알아봅니다.
위 그래프에는 총 6개의 정점(v1, v2, v3, v4, v5 및 v6)이 포함되어 있음을 알 수 있습니다.
학위:
칼리 리눅스 터미널
정점의 각도 v1 = deg(v1) = 1
정점의 각도 v2 = deg(v2) = 1
정점의 차수 v3 = deg(v3) = 1
정점의 각도 v4 = deg(v4) = 5
정점의 각도 v5 = deg(v5) = 1
정점의 각도 v6 = deg(v6) = 0
아웃 학위:
정점의 진출 차수 v1 = deg(v1) = 2
정점의 이탈 차수 v2 = deg(v2) = 3
정점의 진출 차수 v3 = deg(v3) = 2
정점의 진출 차수 v4 = deg(v4) = 0
정점의 진출 차수 v5 = deg(v5) = 2
정점의 진출 차수 v6 = deg(v6) = 0
꼭지점의 정도
위에서 설명한 정의를 통해 정점의 각도 Deg(v) = deg라는 것을 알 수 있습니다.-(v) + 당신+(V). 이제 다음 공식을 사용하여 계산해 보겠습니다.
정점의 차수 v1 = deg(v1) = 1+2 = 3
정점의 차수 v2 = deg(v2) = 1+3 = 4
정점의 각도 v3 = deg(v3) = 1+2 = 3
정점의 각도 v4 = deg(v4) = 5+0 = 5
정점의 각도 v5 = deg(v5) = 1+2 = 3
정점의 각도 v6 = deg(v6) = 0+0 = 0
예시 2:
이 예에는 7개의 정점이 있는 방향성 그래프가 있습니다. 정점 'a'에는 바깥쪽으로 향하는 2개의 모서리, 즉 'ad'와 'ab'가 포함됩니다. 따라서 정점 'a'에는 진출 차수 2가 포함됩니다. 마찬가지로 정점 'a'에는 이 정점 'a'를 향해 다가오는 모서리 'ga'도 있습니다. 따라서 정점 'a'에는 내부 차수(1)가 포함됩니다.
해결책: 위의 모든 정점의 내부 차수와 외부 차수는 다음과 같이 설명됩니다.
학위:
꼭지점의 차수 a = deg(a) = 1
정점의 각도 b = deg(b) = 2
정점 c의 내부 차수 = deg(c) = 2
꼭지점의 내부 차수 d = deg(d) = 1
꼭지점의 차수 e = deg(e) = 1
꼭지점의 각도 f = deg(f) = 1
정점의 각도 g = deg(g) = 0
아웃 학위:
꼭지점의 이탈 차수 a = deg(a) = 2
정점의 이탈 차수 b = deg(b) = 0
정점 c의 이탈 차수 = deg(c) = 1
정점의 이탈 차수 d = deg(d) = 1
꼭지점의 이탈 차수 e = deg(e) = 1
정점의 이탈 차수 f = deg(f) = 1
정점의 이탈 차수 g = deg(g) = 2
각 정점의 차수:
우리는 정점의 각도 Deg(v) = deg라는 것을 알고 있습니다.-(v) + 당신+(V). 이제 다음 공식을 사용하여 계산해 보겠습니다.
정점의 차수 a = deg(a) = 1+2 = 3
정점의 차수 b = deg(b) = 2+0 = 2
정점 c의 차수 = deg(c) = 2+1 = 3
정점의 차수 d = deg(d) = 1+1 = 2
정점의 차수 e = deg(e) = 1+1 = 2
정점의 차수 f = deg(f) = 1+1 = 2
컴퓨터 네트워크의 네트워크 계층
정점의 각도 g = deg(g) = 0+2 = 2
예시 3: 이 예에는 5개의 정점이 있는 방향성 그래프가 있습니다. 정점 'a'에는 바깥쪽으로 향하는 1개의 모서리, 즉 'ae'가 포함됩니다. 따라서 꼭지점 'a'에는 진출 차수 1이 포함됩니다. 마찬가지로 꼭지점 'a'에는 이 꼭지점 'a'를 향해 다가오는 모서리 'ba'도 있습니다. 따라서 정점 'a'에는 내부 차수(1)가 포함됩니다.
100개 중 10개
해결책: 위의 모든 정점의 내부 차수와 외부 차수는 다음과 같이 설명됩니다.
학위
꼭지점의 차수 a = deg(a) = 1
정점의 각도 b = deg(b) = 0
정점 c의 내부 차수 = deg(c) = 2
꼭지점의 내부 차수 d = deg(d) = 1
꼭지점의 차수 e = deg(e) = 1
아웃 학위:
꼭지점의 이탈 차수 a = deg(a) = 1
정점의 이탈 차수 b = deg(b) = 2
정점 c의 이탈 차수 = deg(c) = 0
정점의 이탈 차수 d = deg(d) = 1
꼭지점의 이탈 차수 e = deg(e) = 1
각 정점의 차수:
우리는 정점의 각도 Deg(v) = deg라는 것을 알고 있습니다.-(v) + 당신+(V). 이제 다음 공식을 사용하여 계산해 보겠습니다.
꼭지점의 각도 a = deg(a) = 1+1 = 2
정점의 차수 b = deg(b) = 0+2 = 2
정점 c의 차수 = deg(c) = 2+0 = 2
정점의 차수 d = deg(d) = 1+1 = 2
정점의 차수 e = deg(e) = 1+1 = 2
예시 4: 이 예에는 그래프가 있으며 각 꼭지점의 차수, 내차수, 외차수를 결정해야 합니다.
해결책: 이를 위해 먼저 정점의 내부 차수를 알아낸 다음 정점의 외부 차수를 알아봅니다.
위 그래프에는 총 8개의 정점(0, 1, 2, 3, 4, 5, 6)이 포함되어 있음을 알 수 있습니다.
학위:
정점의 차수 0 = deg(0) = 1
정점의 각도 1 = deg(1) = 2
정점 2의 내부 차수 = deg(2) = 2
꼭지점의 각도 3 = deg(3) = 2
정점의 각도 4 = deg(4) = 2
정점의 각도 5 = deg(5) = 2
정점의 각도 6 = deg(6) = 2
아웃 학위:
정점의 이탈 차수 0 = deg(0) = 2
정점 1의 이탈 차수 = deg(1) = 1
정점 2의 이탈 차수 = deg(2) = 3
CSS 첫 번째 자식
정점 3의 이탈 차수 = deg(3) = 2
정점 4의 진출 차수 = deg(4) = 2
정점의 이탈 차수 5 = deg(5) = 2
정점 6의 진출 차수 = deg(6) = 1
각 정점의 차수:
우리는 정점의 각도 Deg(v) = deg라는 것을 알고 있습니다.-(v) + 당신+(V). 이제 다음 공식을 사용하여 계산해 보겠습니다.
정점의 각도 0 = deg(0) = 1+2 = 3
정점의 차수 1 = deg(1) = 2+1 = 3
정점의 차수 2 = deg(2) = 2+3 = 5
정점의 차수 3 = deg(3) = 2+2 = 4
정점의 차수 4 = deg(4) = 2+2 = 4
정점의 차수 5 = deg(5) = 2+2 = 4
정점의 차수 6 = deg(5) = 2+1 = 3
그래프의 차수 시퀀스
그래프의 차수 순서를 결정하려면 먼저 그래프의 각 꼭지점의 차수를 결정해야 합니다. 그 후에는 이 학위를 오름차순으로 작성하겠습니다. 이 순서/수열은 그래프의 차수 순서라고 할 수 있습니다.
예를 들어: 이 예에는 정점이 3개, 4개, 5개 있는 세 개의 그래프가 있으며 모든 그래프의 차수 시퀀스는 3입니다.
위 그래프에는 3개의 정점이 있습니다. 이 그래프의 순서 정도는 다음과 같이 설명됩니다.
위 그래프에는 4개의 정점이 있습니다. 이 그래프의 차수 순서는 다음과 같습니다.
위 그래프에는 5개의 정점이 있습니다. 이 그래프의 차수 순서는 다음과 같습니다.