이중 그래프의 꼭짓점에 대한 도달 가능성 관계. 이중그래프와 이항 관계

허락하다 V- 유향 그래프의 정점 집합 에프, 이자형- 가장자리가 많습니다. 갈비뼈마다 이자형Î 이자형시작이 있다 V'Î V그리고 끝 V''Î V. 따라서 두 개의 매핑 j 1 과 j 2 가 제공됩니다. 여기서 V'=j 1 ( 이자형) - 갈비뼈의 시작 이자형, V''=j 2 ( 이자형) - 갈비뼈 끝 이자형.

여러 가지 정의가 주어질 수 있습니다 방법이중 그래프에서 에프.

1. 정점과 가장자리의 경로- 이것은 연속이다 엘(V 0 ,이자형 1 ,V 1 ,이자형 2 ,...,엔 엔,vn), 어디 v 나는- 1 =j 1 ( 나는), v 나는=j 2 ( 나는). 꼭지점 V 0이 호출됩니다. 경로의 시작 L,꼭지점 vn - 경로 L의 끝, 숫자 N갈비뼈 - 그의 길이. 하나의 꼭지점으로 구성된 경로의 길이는 0입니다.

2. 가장자리의 경로시퀀스입니다 ( 이자형 1 ,이자형 2 ,...,엔 엔). 이 경로 개념은 무방향 그래프의 경로 개념과 유사합니다.

3. 봉우리에서 가는 길시퀀스입니다 ( V 0 ,V 1 ,...,vn). 정점으로부터의 경로는 여러 간선을 포함하지 않는 그래프에 대해 정의됩니다.

실제로는 주어진 특정 작업에 더 편리한 경로 정의를 사용할 수 있습니다.

경로가 호출됩니다. 지향성 체인(또는 단순히 체인, 이중 그래프만 고려하는 경우), 각 모서리가 1회 이하로 발생하는 경우 단순 지향 체인, 그래프의 각 꼭지점인 경우 에프최대 2개의 모서리에 입사합니다.

예. 길 ( 이자형 5 ,이자형 6 ,이자형 7 ,이자형 1 ,이자형 4 ,이자형 3) (그림 3.11)은 or.chain이고 경로( 이자형 7 ,이자형 1 ,이자형 4 ,이자형 3) - 간단한 작업. 체인.

쌀. 3.11.

경로가 호출됩니다. 지향적인 사이클(또는 단순히 주기, 이중음표만 고려하는 경우) 두 개 이상의 요소로 구성되고 시작 부분이 끝 부분과 일치하는 경우. 무방향 그래프와 마찬가지로 주기의 시작은 일반적으로 고정되어 있지 않습니다. 주기라고 합니다 단순한, 그것에 속하는 각 정점이 정확히 두 개의 가장자리에 입사하는 경우.

예. 길 ( 이자형 1 ,이자형 4 ,이자형 3 ,이자형 2 ,이자형 5 ,이자형 6 ,이자형 7) - 주기, 경로( 이자형 5 ,이자형 6 ,이자형 7) - 간단한 주기.

지향성 사슬과 관련하여 Redei가 2차 장 연구에서 증명한 정리가 유효합니다.

정리 3.3. 허락하다 에프- 각 정점 쌍이 모서리로 연결된 유한 유향 그래프입니다. 그런 다음 에프모든 꼭짓점을 통과하는 단순한 방향의 경로가 있습니다.

ÿ MI 방식으로 증명을 진행하겠습니다. 그래프의 꼭지점 수를 다음과 같이 나타내겠습니다. N.

· N=2: 그래프의 두 꼭지점을 연결하는 호 에프 2, 그래프의 모든 꼭지점을 통과하는 간단한 방향 경로가 있습니다.

· 다음과 같이 가정해보자. N= 중그래프용 FM정리가 맞습니다.

· 이를 증명해 보자. N= 중백작에 +1 FM+1 정리가 정확합니다.

그래프를 만들어보자 FM그래프에 추가하여 +1 FM약간의 피크 vm+1 , 모든 정점에 대한 가장자리가 있음 v 나는 (나=1,2,...,중) 에서 FM. 가정에 따르면 그래프의 모든 꼭지점을 통과하는 간단한 방향 경로가 있습니다. FM: 오후=(V 1 ,V 2 ,...,vm). 꼭지점에 입사하는 모서리의 경우 vm+1, 세 가지 가능성이 있습니다.

1. 호가 있습니다 ( vm +1, V 1). 체인에 추가하기 오후"왼쪽"에서는 그래프의 모든 정점을 통과하는 원하는 체인을 얻습니다. FM +1: 오후 +1 =(vm +1 ,V 1 ,V 2 ,...,vm).

2. 호가 있습니다 ( vm , vm+1). 체인에 추가하기 오후"오른쪽"에서는 그래프의 모든 정점을 통과하는 원하는 체인을 얻습니다. FM +1: 오후 +1 =(vm +1 ,V 1 ,V 2 ,...,vm,vm +1).

3. 열에 있는 경우 FM+1 호가 없습니다 ( vm +1 ,V 1), 호 없음( vm,vm+1), 그런 다음 일부 케이 (케이=2,3,...,중-1) 분명히 호가 있을 것입니다( vk,vm+1) 및 ( vm +1 ,vk+1). 체인을 만들어보자

오후 +1 =(V 1 ,V 2 ,...,vk,vm +1 ,vk +1 ,...,vm).

이 사슬은 그래프의 모든 꼭지점을 통과합니다. FM +1 .

많은 봉우리에서 V태도를 정하자 접근성 R D다음과 같습니다: 상단 V'Î V관계가 있다 R D상단과 함께 V''Î V(이 경우에는 상단이 v''에 접근 가능위에서 V'), 경로가 있는 경우 엘(V',... ,V'') 처음부터 V'그리고 끝 V''.

무방향 그래프의 정점에 대한 연결 관계와 유사하게, 관계는 도달 가능성유향 그래프의 정점에 대해 반사적으로그리고 전이적으로그러나 연결성 관계와 달리 도달가능성 관계는 반드시 대칭일 필요는 없음.

도달 가능성 관계를 사용하여 digraph의 꼭지점 집합을 동등 클래스로 분할하는 것이 결정됩니다. V', V''관계가 대칭이면 동일한 클래스에 속합니다. V''에서 접근 가능 V', ㅏ V'에서 접근 가능 V''.

허락하다 엘 1 (V', ... ,V'') 그리고 엘 2 (V'', ... ,V')는 이러한 정점을 연결하는 해당 경로입니다. 그런 다음 함께 정점을 통과하는 순환을 형성합니다. V'그리고 V''. 따라서 동일한 등가 클래스의 모든 정점은 일부 순환에 속합니다. 그래프에 순환이 없으면 각 등가 클래스는 하나의 꼭지점으로 구성됩니다.

쌀. 3.13.

최소 그래프 에프비, 꼭지점 세트에 대한 유도 V주어진 방향 그래프와 동일한 도달 가능성 관계 에프, 즉. 더 이상 축소할 수 없는 간선 집합이 있는 그래프를 호출합니다. 기초 그래프그래프용 에프.

기본 그래프가 있는 경우 반드시 고유하지는 않습니다. 따라서 그림의 그래프에 대해 3.13, 어느방사형 모서리와 방향성 다각형 주기가 기본 그래프를 정의합니다.

만약에 에프유한 유향 그래프이면 기본 그래프가 존재합니다. "초과" 모서리를 순차적으로 제거하여 얻을 수 있습니다( V 0 ,vn), 모서리가 없는( V 0 ,vn) 지향 체인 아르 자형(V 0 ,vn).

접근성 그래프

그래프를 연구할 때 발생하는 첫 번째 질문 중 하나는 주어진 또는 모든 정점 쌍 사이에 경로가 존재하는지에 대한 질문입니다. 이 질문에 대한 대답은 그래프 G=(V,E)의 정점에 대해 위에서 소개한 도달 가능성 관계입니다. v = w이거나 G가 v에서 w로의 경로를 갖는 경우 정점 w는 정점 v에서 도달할 수 있습니다. 즉, 도달 가능성 관계는 관계 E의 반사적 및 전이적 폐쇄입니다. 무방향 그래프의 경우 이 관계도 대칭이므로 정점 집합 V에 대한 등가 관계입니다. 무방향 그래프에서 등가 클래스는 다음과 같습니다. 도달 가능성 관계와 관련하여 연결된 구성 요소라고 합니다. 유향 그래프의 경우 일반적으로 도달 가능성이 대칭 관계일 필요는 없습니다. 상호 도달성은 대칭적입니다.

정의 9.8.유향 그래프 G=(V,E)의 정점 v와 w는 G가 v에서 w로 가는 경로와 w에서 v로 가는 경로를 갖는 경우 상호 도달 가능하다고 합니다.

상호 도달 가능성 관계는 반사적, 대칭적, 추이적이므로 그래프의 정점 집합에서 동등하다는 것이 분명합니다. 상호 도달 가능성과 관련된 등가 클래스를 강력하게 연결된 구성요소 또는 이중으로 연결된 구성 요소그래프.

먼저 도달가능성 관계를 구축하는 문제를 고려해 보겠습니다. 각 그래프에 대해 도달성 그래프(때때로 전이적 폐쇄 그래프라고도 함)를 정의해 보겠습니다. 이 그래프의 가장자리는 원본 그래프의 경로에 해당합니다.

정의 9.9. G=(V,E)를 유향 그래프로 둡니다. G에 대한 도달 가능성 그래프 G * =(V,E *)는 동일한 정점 세트 V와 다음 간선 세트 E * =( (u, v) | 그래프 G에서 정점 v는 정점 u)에서 도달 가능합니다. .

예제 9.3.예제 9.2의 그래프 G를 생각해 보십시오.

쌀. 9.2.그래프 G

그런 다음 G에 대한 도달성 그래프 G*가 다음과 같은지 확인할 수 있습니다(각 정점 1-5에 대한 새로운 루프 가장자리는 표시되지 않음).

쌀. 9.3.그래프 G*

그래프 G에서 그래프 G*를 어떻게 구성할 수 있나요? 한 가지 방법은 그래프 G의 각 정점에 대해 도달할 수 있는 정점 집합을 결정하고 길이 0, 1, 2 등의 경로로 도달할 수 있는 정점을 순차적으로 추가하는 것입니다.

그래프 G의 인접 행렬 A G와 부울 연산을 기반으로 하는 또 다른 방법을 고려해 보겠습니다. 꼭지점 집합 V=(v 1 , … , vn )이라고 가정합니다. 그러면 행렬 AG는 n × n 부울 행렬입니다.

아래에서는 행렬에 대한 일반적인 연산과의 유사성을 유지하기 위해 부울 연산에 "산술" 표기법을 사용합니다. 즉, 분리를 나타내는 데 +를 사용하고 결합을 나타내는 데 ·를 사용합니다.

n × n 크기의 단위 행렬을 En으로 표시하겠습니다. 넣어보자 . G *를 구성하는 절차를 다음 진술에 기초하도록 하겠습니다.

보조정리 9.2.허락하다 . 그 다음에

증거 k에 대한 귀납법으로 해봅시다.

기초. k=0 및 k=1의 경우 정의에 따라 이 진술은 참입니다.

유도 단계. k에 대해 정리가 참이라고 가정합니다. k+1에 대해서도 유효하다는 것을 보여드리겠습니다. 정의에 따르면 다음과 같습니다.

그래프 G에 v i에서 v j까지 길이가 k+1인 경로가 있다고 가정합니다. 이 경로 중 가장 짧은 경로를 고려해 보겠습니다. 길이가 k이면 귀납 가설 a_(ij)^((k))=1입니다. 또한, jj(1)=1이다. 따라서 aij(k) ajj(1) =1이고 aij(k+1) =1입니다. v i에서 v j까지의 최단 경로 길이가 k+1이면 v r을 두 번째 정점으로 둡니다. 그런 다음 v i에서 v r까지 길이가 k인 경로가 있고 귀납 가설 a ir(k) =1에 의해 이루어집니다. (v r ,v j) E이므로 a_(rj)^((1))=1입니다. 따라서 air(k) arj(1) =1이고 aij(k+1) =1입니다.

반대로, a ij (k+1) =1이면 적어도 하나의 r에 대해 피가수 a ir (k) a rj (1)은 1과 같습니다. 이것이 r=j이면 a ij (k) = 1 그리고 귀납적 가설에 따르면 G는 길이 k의 v i에서 v j까지의 경로를 갖습니다. r j이면 a ir(k) =1이고 a rj(1) =1입니다. 이는 G가 v i에서 v r 길이 k의 경로와 모서리 (v r , v j) E를 갖는다는 것을 의미합니다. 이들을 결합하면 v i에서 v j 길이 k+1의 경로를 얻습니다.

Lemmas 9.1과 9.2에서 우리는 직접적으로 다음을 얻습니다.

결과 1. G=(V,E)를 n개의 꼭지점을 갖는 유향 그래프로 두고 G *를 도달 가능성 그래프로 둡니다. 그러면 A_(G*) = . 증거. Lemma 5.1에 따르면 G에 u에서 vu로 가는 경로가 있으면 여기에는 길이 n-1인 u에서 v로 가는 간단한 경로도 포함됩니다. 그리고 Lemma 5.2에서는 이러한 모든 경로가 매트릭스에 표시됩니다.

따라서 G에 대한 도달성 그래프의 인접 행렬 A G*를 구성하는 절차는 행렬을 n-1 승으로 올리는 것으로 축소됩니다. 이 절차를 단순화하기 위해 몇 가지 설명을 하겠습니다.

여기서 k는 2kn이 되는 가장 작은 숫자입니다.

a ir = 1이고 a rj = 1인 r이 발견되면 전체 합 a ij (2) = 1이 됩니다. 따라서 나머지 용어는 무시할 수 있습니다.

예제 9.3.예를 들어, 다음에 제시된 그래프 G에 대한 도달 가능성 그래프 A G*의 행렬 계산을 고려해 보겠습니다. 그림 9.2. 이 경우

G에는 6개의 꼭지점이 있으므로 . 이 행렬을 계산해 보겠습니다.

그리고 (마지막 평등은 확인하기 쉽습니다). 따라서,

보시다시피, 이 행렬은 실제로 다음과 같은 그래프를 정의합니다. 그림 9.3.

상호 도달 가능성, 강력하게 연결된 구성 요소 및 그래프 기반

도달 가능성 그래프와 유사하게 강력한 도달 가능성 그래프를 정의합니다.

정의 9.10. G=(V,E)를 유향 그래프로 둡니다. G에 대한 강력한 도달 가능성 그래프 G * * =(V,E * *)는 동일한 정점 집합 V와 다음 간선 집합 E * * =( (u, v) | 그래프 G에서 정점 v 및 u를 갖습니다. 상호 도달 가능).

도달가능성 그래프의 행렬을 이용하면 강한 도달가능성 그래프의 행렬을 쉽게 구성할 수 있다. 실제로, 도달 가능성과 강한 도달 가능성의 정의에 따르면 모든 쌍 (i,j), 1 i,j n에 대해 두 요소 A G* (i, j) 및 A G가 모두 있는 경우에만 요소의 값이 1입니다. * (j, i)는 1과 같습니다. 즉

행렬을 기반으로 그래프 G의 강하게 연결된 구성 요소를 다음과 같이 식별할 수 있습니다.

A_(G_*^*)(1,j) = 1이 되도록 구성요소 K 1 꼭지점 v 1과 모든 꼭지점 v j를 배치하겠습니다.

구성요소 K 1, …, Ki 및 v k가 이미 구성되었다고 가정합니다. 이는 아직 구성요소에 포함되지 않은 최소 개수의 꼭지점입니다. 그런 다음 구성요소 K_(i+1)에 정점 v k와 모든 정점 v j를 배치합니다.

A_(G_*^*)(k,j) = 1입니다.

모든 정점이 구성 요소에 분산될 때까지 단계 (2)를 반복합니다.

우리의 예에서 그래프 G의 경우 그림 2행렬로부터 우리는 강한 도달 가능성 그래프의 다음 행렬을 얻습니다.

위에서 설명한 절차를 사용하여 그래프 G의 꼭지점은 강한 연결성의 4가지 구성 요소로 나누어집니다. K 1 = (v 1, v 2, v 3), \ K 2 =( v 4), \ K 3 =( v 5), \ K 4 =( v 6 ). 강하게 연결된 구성 요소 집합에서 도달 가능성 관계도 정의합니다.

정의 9.11. K와 K"를 그래프 G의 강하게 연결된 구성 요소로 둡니다. 구성 요소 K 에서 접근 가능 K= K"이거나 v에서 u에 도달할 수 있는 두 개의 정점 u K와 v K"가 있는 경우 구성 요소 K^\prime 케이 엄격하게 달성 가능 K K"이고 K가 K"에서 도달할 수 있는 경우 K^\프라임입니다. 성분 K는 다음과 같습니다. 최저한의,어떤 구성요소에서도 엄격하게 접근할 수 없는 경우.

한 구성 요소의 모든 정점은 상호 도달 가능하므로 구성 요소의 도달 가능성과 엄격한 도달 가능성의 관계는 정점 u K 및 v K의 선택에 의존하지 않는다는 것을 쉽게 이해할 수 있습니다.

엄격한 도달가능성의 다음 특성은 정의에서 쉽게 추론됩니다.

보조정리 9.3.엄격한 도달 가능성 관계는 부분 순서 관계입니다. 그것은 반사 방지, 반대칭 및 추이적입니다.

이 관계는 정점이 구성 요소인 유향 그래프로 표현될 수 있으며, 간선(K", K)은 K가 K"에서 엄격하게 도달할 수 있음을 의미합니다. ~에 쌀. 9.4이 구성 요소 그래프는 위에서 고려한 그래프 G에 대해 표시됩니다.

쌀. 9.4.

이 경우 최소 성분 K 2 가 하나 있습니다.

많은 응용 프로그램에서 방향성 그래프는 제품, 상품, 정보 등 일부 리소스의 유통 네트워크를 나타냅니다. 그러한 경우, 이 리소스가 네트워크의 어느 지점으로든 전달될 수 있는 지점(정점)의 최소 수를 찾는 작업이 자연스럽게 발생합니다.

정의 9.12. G=(V,E)를 유향 그래프로 둡니다. 정점 W V의 부분 집합을 호출합니다. 생성, W의 정점에서 그래프의 정점에 도달할 수 있는 경우 꼭짓점 W V 의 하위 집합이 생성되는 경우 그래프의 기본이라고 부르지만, 해당 하위 집합은 생성되지 않습니다.

다음 정리를 사용하면 그래프의 모든 밑수를 효율적으로 찾을 수 있습니다.

정리 9.1. G=(V,E)를 유향 그래프로 둡니다. 꼭짓점 WV의 하위 집합은 G의 각각의 최소 강하게 연결된 구성 요소에서 하나의 꼭지점을 포함하고 다른 꼭지점을 포함하지 않는 경우에만 G의 기본입니다.

증거먼저 그래프의 각 정점은 일부 최소 구성 요소에 속하는 정점에서 도달할 수 있다는 점을 알아두세요. 따라서 각 최소 구성 요소에서 하나의 정점을 포함하는 정점 집합 W가 생성되고, 정점 집합에서 임의의 정점이 제거되면 해당 최소 구성 요소의 정점에 도달할 수 없게 되므로 더 이상 생성되지 않습니다. 그러므로 W는 염기이다.

반대로, W가 기본인 경우 각 최소 구성 요소의 정점을 하나 이상 포함해야 합니다. 그렇지 않으면 이러한 최소 구성 요소의 정점에 액세스할 수 없습니다. W는 다른 정점을 포함할 수 없습니다. 각 정점은 이미 포함된 정점에서 도달할 수 있기 때문입니다.

이 정리로부터 그래프 G를 하나 구성하거나 모든 밑수를 열거하는 다음 절차를 따릅니다.

G의 강력하게 연결된 구성요소를 모두 찾습니다.

순서를 결정하고 이 순서와 관련된 최소 구성 요소를 선택합니다.

각 최소 구성 요소에서 하나의 꼭지점을 선택하여 그래프의 하나 또는 모든 기본을 생성합니다.

예제 9.5.그림에 표시된 방향 그래프 G의 모든 기본을 정의하겠습니다. 그림 9.5.

쌀. 9.5.그래프 G

첫 번째 단계에서는 G의 강력하게 연결된 구성 요소를 찾습니다.

두 번째 단계에서는 이러한 구성 요소에 대한 엄격한 도달 가능성 그래프를 구성합니다.

쌀. 9.6. G 구성 요소의 도달 가능성 관계 그래프

최소 구성요소를 정의합니다: K 2 = ( b ), K 4 = ( d, e, f, g) 및 K 7 = ( r).

마지막으로 G의 네 가지 기본을 모두 나열합니다. B 1 = ( b, d, r), B 2 = ( b, e, r), B 3 = ( b, f, r) 및 B 1 = ( b, g, r) .

작업

문제 9.1.임의의 방향 그래프의 모든 꼭지점의 차수의 합이 짝수임을 증명하십시오.

이 문제는 대중적인 해석을 가지고 있습니다. 총 수파티에 오는 사람들 사이에는 항상 짝수의 악수가 교환됩니다.

문제 9.2.최대 4개의 꼭지점을 갖는 모든 비동형 무방향 그래프를 나열합니다.

문제 9.3.일부 간선을 제거한 후에도 방향이 없는 연결된 그래프가 연결된 상태로 유지됨 ← 이 간선이 일부 순환에 속함을 증명하십시오.

문제 9.4. n개의 꼭짓점을 갖는 무방향 연결 그래프를 증명하세요.

최소한 n-1개의 간선을 포함합니다.

n-1개보다 많은 모서리가 포함되어 있으면 적어도 하나의 주기가 있습니다.

문제 9.5. 6명으로 구성된 그룹에는 아는 사람이 세 쌍 또는 낯선 사람이 세 쌍 있다는 것을 증명하십시오.

문제 9.6.무방향 그래프 G=(V,E)가 연결되어 있음을 증명하십시오. 각 파티션 V= V 1 V 2 비어 있지 않은 V 1 및 V 2 V 1 과 V 2 를 연결하는 모서리가 있습니다.

문제 9.7.무방향 그래프에 정확히 두 개의 홀수차 정점이 있는 경우 두 정점이 경로로 연결되어 있음을 증명하세요.

문제 9.8. G=(V,E)를 |E|를 사용하는 무방향 그래프로 설정합니다.< |V|-1. Докажите, что тогда G несвязный граф.

문제 9.9.연결된 무방향 그래프에서 임의의 두 가지를 증명하십시오. 간단한 방법최대 길이의 공통 꼭지점을 갖습니다.

문제 9.10.루프 G=(V,E)가 없는 무방향 그래프에 k개의 연결된 구성요소가 있다고 가정합니다. 그럼 그걸 증명해봐

문제 9.11.도달 가능성 그래프의 용도 결정

n개의 꼭짓점과 빈 간선 집합을 가진 그래프

n개의 꼭지점을 갖는 그래프: V= (v 1 ,… , v n ), 그 변은 순환을 형성합니다:

문제 9.12.그래프에 대한 도달 가능성 그래프 행렬 계산

해당 도달 가능성 그래프를 구성합니다. 그래프 G의 밑변을 모두 찾아보세요.

문제 9.13.주어진 환경에 맞게 구축 쌀. 9.7유향 그래프 G 1 =(V,E) 인접 행렬 A G1, 입사 행렬 B G1 및 인접 목록. 도달 가능성 행렬 A G1*을 계산하고 해당 도달 가능성 그래프 G1*을 구성합니다.

쌀. 9.7.

방향이 없는 트리와 방향이 있는 트리

트리는 다양한 유형의 계층 구조를 나타내는 데 사용되는 가장 흥미로운 그래프 클래스 중 하나입니다.

정의 10.1.무방향 그래프가 연결되어 있고 순환이 없으면 트리라고 합니다.

정의 10.2.방향 그래프 G=(V,E)는 다음과 같은 경우 (방향) 트리라고 합니다.

~에 쌀. 10.1무방향 트리 G 1 과 방향 트리 G 2 의 예가 표시됩니다. 트리 G2는 정점 c를 루트로 선택하고 루트에서 멀어지는 방향으로 모든 가장자리의 방향을 지정하여 G1에서 파생됩니다.

쌀. 10.1.방향이 없는 트리와 방향이 있는 트리

이것은 우연이 아닙니다. 방향이 없는 트리와 방향이 있는 트리 사이의 관계에 대한 다음 설명을 스스로 증명하십시오.

정리 10.1.방향이 지정되지 않은 트리 G=(V,E)에서 임의의 정점 v V를 루트로 선택하고 모든 가장자리의 방향을 "루트에서" 방향으로 지정합니다. 즉, v를 그것에 입사하는 모든 가장자리의 시작, v에 인접한 정점을 그것에 입사하는 아직 방향이 지정되지 않은 모든 가장자리의 시작 등으로 만들면 결과 방향 그래프 G"는 방향이 있는 트리가 됩니다.

방향이 없는 나무와 방향이 있는 나무는 많은 동등한 특성을 가지고 있습니다.

정리 10.1. G=(V,E)를 무방향 그래프로 둡니다. 그러면 다음 조건은 동일합니다.

G는 나무이다.

G의 임의의 두 꼭짓점에는 이를 연결하는 고유한 경로가 있습니다.

G는 연결되어 있지만 E에서 모서리를 제거하면 연결이 중단됩니다.

G는 연결되어 있고 |E| = |V| -1.

G는 비순환이고 |E| = |V| -1.

G는 비순환적이지만 E에 간선을 추가하면 순환이 생성됩니다.

증거(1) (2): G의 일부 두 정점이 두 경로로 연결되어 있다면 분명히 G는 사이클을 갖게 됩니다. 그러나 이는 (1)의 트리 정의와 모순됩니다.

(2) (3): G가 연결되어 있지만 일부 간선(u,v)이 제거되면 E는 연결성을 잃지 않으며 u와 v 사이에는 이 간선을 포함하지 않는 경로가 있습니다. 그러나 G에는 u와 v를 연결하는 경로가 두 개 이상 있으며 이는 조건 (2)와 모순됩니다.

(3) (4): 독자에게 제공됩니다(문제 9.4 참조).

(4) (5): G가 사이클을 포함하고 연결되어 있으면 사이클에서 간선을 제거할 때 연결성이 끊어져서는 안 되지만 간선은 |E|= V -2로 유지되며 문제 9.4에 따르면 (a) 최소한 V -1 개의 리브가 있어야 합니다. 결과적인 모순은 G에 사이클이 없으며 조건 (5)가 충족된다는 것을 보여줍니다.

(5) (6): E에 간선 (u,v)를 추가해도 순환이 발생하지 않는다고 가정합니다. 그런 다음 G의 정점 u와 v는 서로 다른 연결된 구성 요소에 있습니다. |E|= V -1이므로 이러한 구성 요소 중 하나에서 (V 1 ,E 1)이라고 가정하면 모서리 수와 꼭지점 수가 일치합니다. |E 1 |=|V 1 |. 그러나 G의 비주기성과 모순되는 주기(문제 9.4(b) 참조)가 있습니다.

(6) (1): G가 연결되지 않은 경우 서로 다른 연결된 구성 요소에서 두 개의 꼭지점 u와 v가 있게 됩니다. 그러면 E에 간선(u,v)을 추가해도 순환이 나타나지 않으며 이는 (6)과 모순됩니다. 따라서 G는 연결되어 있고 트리이다.

유향 트리의 경우 다음과 같은 귀납적 정의를 사용하는 것이 종종 편리합니다.

정의 10.3.유도를 통해 트리라고 불리는 유향 그래프 클래스를 정의해 보겠습니다. 동시에, 각각에 대해 선택된 정점, 즉 루트를 정의합니다.

쌀. 10.2이 정의를 보여줍니다.

쌀. 10.2.지향성 트리의 귀납적 결정

정리 10.2.방향성 트리 10.2와 10.3의 정의는 동일합니다.

증거그래프 G=(V,E)가 정의 10.2의 조건을 만족한다고 가정합니다. 정점 수 |V|에 대한 귀납법을 통해 보여드리겠습니다.

|V|=1이면 유일한 정점 v V는 속성(1)에 따라 트리의 루트입니다. 즉, 이 그래프에는 간선이 없습니다. E = . 그 다음에 .

정의 10.2를 만족하는 n개의 정점을 가진 모든 그래프가 에 포함된다고 가정합니다. (n+1)번째 꼭지점을 갖는 그래프 G=(V,E)가 정의 10.2의 조건을 만족한다고 가정합니다. 조건 (1)에 따라 정점 루트 r 0 을 갖습니다. k 개의 모서리가 r 0 에서 나오고 정점 r 1 , ... , r k (k 1)로 이어진다고 가정합니다. 정점 Vi =( v V|v \textit( )r i 에서 도달 가능)과 이를 연결하는 간선 E i E를 포함하는 그래프를 G i ,(i=1, …, k)로 표시하면 이해하기 쉽습니다. Gi는 정의 10.2의 조건을 만족합니다. 실제로, ri는 간선을 포함하지 않습니다. 즉, 이 꼭짓점은 G i의 루트입니다. V i의 나머지 정점 각각은 G에서와 같이 하나의 간선을 포함합니다. v Vi 이면 그래프 G i 의 정의에 따라 루트 r i 에서 도달할 수 있습니다. 이후 |V i | n, 귀납적 가설에 의해 . 그런 다음 그래프 G는 트리 G 1, ..., G k에서 정의 10.3의 귀납적 규칙 (2)에 따라 얻어지며 따라서 클래스에 속합니다.

⇐ 일부 그래프 G=(V,E)가 클래스 에 포함되면 이에 대한 정의 10.2의 조건 (1)-(3)의 충족은 정의 10.2를 사용한 귀납법에 의해 쉽게 확립될 수 있습니다. 우리는 이것을 독자들에게 연습으로 남겨 둡니다.

식물학과 가족 관계 분야라는 두 가지 출처에서 나온 방향성 나무와 관련된 용어가 풍부합니다.

루트는 가장자리가 없는 유일한 정점이고, 잎은 가장자리가 없는 유일한 정점입니다. 뿌리에서 잎까지의 길을 나무의 가지라고 합니다. 나무의 높이는 가지의 최대 길이입니다. 정점의 깊이는 루트에서 해당 정점까지의 경로 길이입니다. 정점 v V에 대해, v에서 도달할 수 있는 모든 정점과 이를 연결하는 E의 간선을 포함하는 트리 T=(V,E)의 하위 그래프는 루트 v를 갖는 트리 T의 하위 트리 Tv를 형성합니다(문제 10.3 참조). 정점 v의 높이가 트리 T v의 높이입니다. 여러 개의 분리된 트리가 결합된 그래프를 포레스트(forest)라고 합니다.

모서리가 정점 v에서 정점 w로 이어지는 경우 v가 호출됩니다. 아버지승, 그리고 승 - 아들 v (최근에는 영문학에서 부모-자식이라는 무성애 용어 쌍이 사용되었습니다). 트리의 정의에 따르면 루트 외에 각 꼭지점에는 단일 아버지가 있습니다. 경로가 정점 v에서 정점 w로 이어지는 경우 v를 w의 조상이라고 하고 w를 v의 자손이라고 합니다. 공통 아버지를 갖는 정점을 호출합니다. 형제또는 자매.

지향 트리(지향 비순환 트리)를 일반화하는 또 다른 종류의 그래프를 강조해 보겠습니다. 이러한 레이블이 지정된 그래프의 두 가지 유형은 나중에 부울 함수를 나타내는 데 사용됩니다. 이러한 그래프에는 여러 개의 루트(모서리를 포함하지 않는 꼭지점)가 있을 수 있으며, 각 꼭지점은 트리처럼 하나가 아닌 여러 개의 모서리를 포함할 수 있습니다.

컴퓨터 기술, 특히 프로그램 ... 2009 올해의 초등학교실험 장소이다 에 의해연방 소개 상태 ...

M MEDIA MONITORING 직업교육 현대화 2011년 3~8월

요약

유나이티드 상태시험 " 에 의해선택": 정보용 컴퓨터기술, 생물학 및 문학. 그런데 이에 년도통합국가시험... 질문"실시 결과에 대해 프로그램들국립 연구 대학의 발전 2009 -2010 연령". ...

전략적 개발 프로그램 Tver 2011

프로그램

안에 2009 년도. 2010년에 관찰된 구조적 변화 년도에 의해...쪽으로 2009 , ... 전문적으로 – 지향 외국어", "현대 교육 기술". 각 프로그램고급 교육 모듈이 구현되고 있습니다. 상태 ...

1. 도달 가능성과 반대 달성 가능성

도달가능성(reachability) 개념을 사용하는 문제는 꽤 많다. 여기에 별명 중 하나가 있습니다. 그래프는 사람이 정점으로 표시되고 호가 통신 채널을 해석하는 일종의 조직 모델이 될 수 있습니다. 이러한 모델을 고려할 때 한 사람 x의 정보가 다른 사람 x 7에게 전송될 수 있는지 여부에 대한 의문이 제기될 수 있습니다. 정점 x에서 정점 X/로 가는 경로가 있습니까? 그러한 경로가 존재하는 경우 정점 x는 정점 x에서 도달 가능하다고 합니다. 길이가 주어진 값을 초과하지 않거나 길이가 그래프의 최대 정점 수보다 작은 경로에서만 정점 x에서 정점 x의 도달 가능성에 관심이 있을 수 있습니다.

그래프의 연결 가능성은 연결 가능성 행렬 R = ||r,y||로 설명됩니다. 나, j =1,2,... 피,어디 피는 그래프의 정점 개수이며 각 요소는 다음과 같이 정의됩니다.

구-정점인 경우 1 엑스, x에서 접근 가능,

구=그렇지 않으면 0입니다.

주어진 정점 x'에서 도달할 수 있는 그래프 G의 정점 집합 R(x,)는 다음 요소 x로 구성됩니다. , 도달 가능성 행렬의 (/, /)번째 요소는 1과 같습니다. 분명히 행렬 R의 모든 대각선 요소는 1과 같습니다. 왜냐하면 각 꼭지점은 길이가 0인 경로를 통해 자체적으로 도달할 수 있기 때문입니다. 1차 Г +1(x,)의 직접 매핑은 이러한 정점의 집합이므로 XJ,길이 1의 경로를 사용하여 x에서 도달할 수 있는 경우 세트 Г(Г(x,)) = Г 엑스,)길이가 2인 경로를 사용하여 x에서 도달할 수 있는 정점으로 구성됩니다. G와 유사합니다. 피(x,)길이의 경로를 사용하여 x에서 도달할 수 있는 정점 집합입니다. 아르 자형.

x에서 도달할 수 있는 그래프의 모든 정점은 길이가 0, 1, 2인 경로를 사용하여 도달할 수 있어야 하기 때문에... 또는 아르 자형이면 정점 x'에 도달할 수 있는 정점 집합은 다음 형식으로 표현될 수 있습니다.

보시다시피, 도달 가능한 정점 세트 R(x,)는 정점 x'의 직접 전이적 폐쇄를 나타냅니다. R(x,) = T(x,). 결과적으로 도달 가능성 행렬을 구성하기 위해 모든 정점 x, e X에 대해 도달 가능한 집합 R(x,)를 찾습니다. y y - x 7 e R(x,)인 경우 1이고 구-그렇지 않으면 0입니다. 그림에 표시된 그래프의 경우 59.4, ㅏ, 도달 가능성 세트는 다음과 같이 찾을 수 있습니다.

쌀. 59.4.

인접성(A), 도달성(R), 대응성(Q) 행렬의 형식은 다음과 같습니다.

대응 가능성 매트릭스 Q = qij,i,j= 1,2,... 피,어디 피- 그래프의 정점 수는 다음과 같이 결정됩니다.

qij= 1, 정점 xy에서 정점에 도달하는 것이 가능하다면 xh qtj =그렇지 않으면.

대응 가능 세트 질문(x,)는 이 집합의 임의 정점에서 정점 X/에 도달할 수 있는 정점 집합입니다. 도달 가능한 집합 R(x,)를 구성하는 것과 유사하게 다음과 같은 표현식을 작성할 수 있습니다. 질문(x,):

따라서 Q(x,)는 정점 x의 역 추이적 폐쇄에 지나지 않는다는 것이 분명합니다. Q(x() = T"(x,). 정의로부터 열 X, 행렬 Q(여기서 qtj = xyQ(x,)인 경우 1이고, s/u=0그렇지 않은 경우)는 행렬 R의 x행과 일치합니다. 즉, Q = R. 여기서 R은 도달 가능성 행렬 R로 전치된 행렬입니다.

카운터 도달 가능성 매트릭스는 앞서 표시되었습니다.

행렬 R과 Q의 모든 요소는 1 또는 0과 같기 때문에 각 행은 이진 형식으로 저장되어 컴퓨터 메모리 비용을 절약할 수 있습니다. 행렬 R과 Q는 계산 측면에서 주요 연산이 고속 논리 연산이기 때문에 컴퓨터 처리에 편리합니다.

2. 경로에 포함된 정점 집합 찾기 이러한 경로에 포함된 그래프 정점에 대해 알아내려면 직접 및 역전이 클로저의 정의를 기억해야 합니다. T + (x,)는 정점 x에서 경로가 있는 정점 집합이고 T"(Y)는 x /로 가는 경로가 있는 정점 집합이므로 T (x,) n T (xj)- 각각 x에서 xy로 가는 적어도 하나의 경로에 속하는 정점 세트. 이러한 꼭짓점은 두 끝 꼭짓점과 관련하여 필수 또는 필수라고 합니다. 엑스,그리고 후. 그래프의 다른 모든 정점은 중요하지 않거나 중복된다고 합니다. 제거해도 x/에서 xy로의 경로에 영향을 주지 않기 때문입니다.

따라서 그림의 그래프에 대해 59.5, 예를 들어 정점 X2에서 정점 X4까지 경로에 포함된 정점을 찾는 것은 T + (xg) = (xg, x3, X4, X5, Xb), T "(x4) = (xi)를 찾는 것으로 귀결됩니다. , X2, X3 , X4, X5) 및 해당 교차점 T + (xr) n T(x4) = = (X2, X3, X4, X 5).