그래프 및 용어. 그래프 및 용어 그래프 정점 유형
강의 4. 그래프
4.1.그래프. 정의, 그래프 유형
4.2. 그래프의 속성
프로그램 조항
그래프 이론에 대한 관심이 높아지는 데에는 몇 가지 이유가 있습니다. 그래프 이론이 물리학, 화학, 통신 이론, 컴퓨터 디자인, 전기 공학, 기계 공학, 건축, 운영 연구, 유전학, 심리학, 사회학, 경제학, 인류학, 언어학 등의 분야에서 사용되고 있다는 것은 부인할 수 없는 사실입니다. 이 이론은 또한 그룹 이론, 행렬 이론, 수치 분석, 확률 이론, 위상수학 및 조합 분석을 포함한 수학의 여러 분야와 밀접하게 관련되어 있습니다. 그래프 이론이 이진 관계를 포함하는 모든 시스템에 대한 수학적 모델 역할을 한다는 것도 확실합니다. 그래프는 다이어그램으로 표현되기 때문에 매력적이고 심미적으로 좋습니다. 그래프 이론에는 본질적으로 초보적인 많은 결과가 포함되어 있지만, 또한 가장 정교한 수학자들이 주목할 만한 매우 미묘한 조합 문제도 엄청나게 풍부하게 포함하고 있습니다. (F. 하라리 “그래프 이론”)
응용문제에서 그래프의 활용 편의성과 폭넓은 활용 가능성에 주목
문학
보안 질문
- 그래프란 무엇입니까?
- 그래프의 꼭지점과 변을 무엇이라고 하나요?
3. 연필을 떼지 않고 가장자리를 두 번 통과하지 않고 이 다이어그램을 따라 그리는 것이 가능합니까?
- 그래프의 꼭짓점 차수의 합이 홀수가 될 수 있나요?
- 11개 팀이 토너먼트를 조직하여 각 팀이 정확히 5경기를 치르는 것이 가능합니까?
6. 단락 4.1.(6)의 정의가 동일함을 보여주십시오(동일한 객체를 설명함).
7. 그래프가 동형임을 보여라.
8. 동형이 그래프에서 등가 관계임을 보여주십시오.
9. 큐브 프레임을 만들기 위해 와이어 조각을 나누어야 하는 최소 부품 수는 얼마입니까?
10. 그래프가 평면임을 보여라.
그래프. 정의, 그래프 유형
그래프 이론의 아버지는 L. Euler A707-1782입니다. 그는 1736년에 당시 널리 알려진 문제인 Königsberg 교량 문제를 해결했습니다.
쾨니히스베르크(Koenigsberg) 시에는 그림과 같이 프레골리아(Pregolya) 강 유역과 서로 7개의 다리로 연결된 두 개의 섬이 있었습니다. 4.1.(1) (A,D – 섬, B,C – 강둑). 임무는 다음과 같습니다. 땅의 네 부분을 모두 통과하는 경로를 찾는 것입니다. 이 경로는 어느 곳에서나 시작하여 같은 부분에서 끝나고 각 다리를 정확히 한 번씩 통과합니다. 물론 이 문제를 모든 경로를 검색하여 경험적으로 해결하려고 시도하는 것은 쉽지만 모든 시도는 실패로 끝날 것입니다. L. Euler는 그러한 경로가 불가능하다는 것을 증명함으로써 이 문제에 대한 해결책을 찾았습니다.
문제에 대한 해결책이 없음을 증명하기 위해 오일러는 토지의 각 부분을 점(꼭지점)으로 지정하고 각 다리를 해당 점을 연결하는 선(모서리)으로 지정했습니다. 결과는 "그래프"입니다. 이 그래프는 그림 1에 나와 있습니다. 4.1.(2), 여기서 포인트
그림 4의 초밥 4개와 동일한 문자가 표시되어 있습니다. 4.1(1). 이 문제에 대한 "긍정적인" 해결책이 존재하지 않는다는 진술은 특별한 방법으로 그림 1에 제시된 그래프를 탐색하는 것이 불가능하다는 진술과 동일합니다. 4.1(2).
이 경우 문제는 다음 공식을 따릅니다. 모든 정점에서 시작하여 각 가장자리를 한 번만 통과하고 원래 정점으로 돌아갑니다.
그래프 이론을 사용하여 모델링할 수 있는 또 다른 문제의 예는 세 집에 세 가지 유형의 유틸리티를 공급하는 문제입니다. 문제에 따르면 세 집은 각각 지하 파이프 라인과 케이블을 통해 물, 가스, 전기 등 세 가지 유형의 유틸리티에 연결되어야 합니다. 문제는 공급선을 넘지 않고 이 세 주택에 유틸리티를 제공하는 것이 가능한지 여부입니다. 이 문제를 모델링한 그래프가 그림 1에 나와 있습니다. 4.1(3) (이 잘 알려진 모델 문제는 때때로 주택과 우물에 관한 문제로 공식화됩니다.)
초소형 회로를 만들 때 보다 실용적인 성격의 유사한 문제가 발생합니다. 각 레벨에서 와이어를 교차시키는 것은 바람직하지 않습니다.
정의 4.1(1)
그래프는 꼭짓점 집합이라고 하는 유한 집합 V와 집합 V의 요소 2개 부분 집합으로 구성된 집합 E입니다. 집합 E를 간선 집합이라고 합니다. 집합 E의 원소를 간선(edge)이라고 합니다. 그래프는 G(V, E)로 표시됩니다. 세트 V의 요소 a와 b는 연결됨(connected) 또는 에지(a, b)에 의해 연결됨(connected by a edge)이라고 합니다.
즉, 그래프는 점들로 구성된 도형이며, 그 중 일부는 선분으로 연결되어 있습니다.
그래프의 예로는 지하철 지도, 가계도, 로드맵 등이 있습니다.
정의 4.1(2)
(a, b)가 간선이면 정점 a와 b를 간선 (a, b)의 끝이라고 합니다. 간선(a, b)라고도 합니다. 부대정점 a와 b에. 반대로 정점 a와 b가 가장자리(a, b)에 입사한다고 말합니다. 두 개의 봉우리가 불린다. 인접한 (이웃), 그것이 모서리의 끝인 경우, 또는 동일한 모서리에 입사하는 경우 동일합니다. 두 모서리가 공통 꼭지점에 입사하면 인접하다고 합니다.
두 점 사이에 여러 개의 간선이 허용되는 경우 그래프를 호출합니다. 다중 그래프.
그래프의 모든 정점이 인접하면 그래프를 호출합니다. 완벽한.
꼭지점은 1개이고 간선은 없는 그래프(1개의 점-꼭지점으로 구성)를 호출합니다. 하찮은.
정의 4.1(3)
정점 v의 차수는 deg(v)로 표시되며, 이는 이 정점에 입사하는(여기서 나오는) 모서리의 수입니다.
차수가 0인 꼭짓점(즉, 꼭짓점에서 가장자리가 나오지 않고 "외로운" 점임)을 고립이라고 합니다.
1차 꼭지점을 매달린 꼭지점이라고 합니다.
꼭짓점은 짝수일 수도 있고 홀수일 수도 있습니다.
정의 4.1.(4)
경로(정점 간) – 일련의 가장자리와 이를 연결하는 중간 정점
경로 길이 – 경로에 포함된 가장자리 수
단순 경로(Simple Path)는 모든 모서리와 꼭짓점이 구별되는 경로입니다.
사이클(루프)은 끝과 일치하는 시작을 제외한 모든 정점이 다른 0이 아닌 길이의 닫힌 경로입니다.
예제 4.1(1).
1. 정점 세트 V = (a,b,c)와 모서리 세트 E ((a, b), (b, c))를 갖는 그래프는 그림 4.1(4)와 같이 묘사될 수 있습니다. ) 정점 a와 c 사이의 경로에는 가장자리 (a,b), (b,c)와 정점 c가 포함됩니다.
참고: 두 사진 모두 동일한 상황을 반영합니다. 그래프의 관점에서 가장 먼저 중요한 것은 점 간의 연결 여부이지 기하학이 아닙니다.
2. V = (a,b,c,d,e) 및 E = ((a, b), (a, e), (b, e), (b, d), (b, c)인 그래프 ), (CD)),
그림에 표시된 다이어그램으로 묘사할 수 있습니다. 4.1.(5). 그래프에는 두 개의 사이클(b, e, a), (b, c, d)이 포함되어 있습니다.
3. 그림에서 4.1.(6) 정점 a와 c는 인접하고 e 1, e 2 및 e 3은 인접 가장자리이고 정점 a와 f는 인접하지 않으며 e 2와 e 5는 인접 가장자리가 아닙니다. 정점 b, c, d의 차수는 2이고 정점 a와 f의 차수는 3입니다.
이제 오일러의 문제로 돌아가 보겠습니다. 그래프를 탐색할 때 두 가지 상황이 가능합니다. 경로의 시작과 끝이 동일하고 입력과 출력이 다릅니다. 그에 따라 그래프를 살펴보려면(연필을 떼지 않고 가장자리를 두 번 건너뛰거나 추적하지 않고 그림에 원을 그립니다):
첫 번째 경우에는 모든 정점의 각도가 짝수여야 하고, 두 번째 경우에는 입구와 출구를 제외한 모든 정점이 짝수여야 합니다.
예제 4.1.(2)
그림 1의 그래프를 통해 갈 수 있습니까? 4.1(4), 건너뛰거나 가장자리를 두 번 통과하지 않고?
차수가 3인 정점 c와 j를 제외하고 모든 정점의 차수는 짝수입니다. 따라서 유일한 순회 경로는 정점 c와 j를 시작과 끝으로 사용하는 경로입니다(또는 그 반대).
대부분의 경우 가장자리가 기본적으로 일방통행인 그래프가 필요합니다. 즉, 모서리가 꼭지점 a에서 꼭지점 b로 가는 것으로 간주되면 꼭지점 b에서 꼭지점 a로 가는 것을 고려할 수 없습니다. 예를 들어, 그래프가 파이프라인의 석유 흐름을 모델링하고 석유가 a 지점에서 b 지점으로 흐른다면 우리는 석유가 b 지점에서 a 지점으로 반대 방향으로 흐르기를 원하지 않을 것입니다.
정의 4.1(5)
방향 그래프 또는 유향 그래프 G G(V, E)로 표시되는 는 꼭짓점 집합 V와 Y의 요소 순서쌍 집합 E로 구성되며, 그래프가 방향이 있는 것이 분명한 경우 방향이 지정된 가장자리 집합 또는 간단히 가장자리라고 합니다. 집합 E의 요소를 방향이 있는 모서리라고 합니다. 이면 a를 간선(a, b)의 초기 꼭짓점, b를 최종 꼭짓점이라고 합니다.
예제 4.1(3)
V = (a, b, c, d] 및 E = ((a, b), (b, c), (c, c), (c, d), (d,b),( c,d),(d,a))는 그림 1에 나와 있습니다.
정의 4.1.(6)
나무 그래프에 대한 몇 가지 동등한 정의를 고려해 보겠습니다.
1) 순환이 없는 연결 그래프입니다(연결성 속성에 대해서는 4.2 참조).
2) 임의의 두 정점이 단순 경로로 연결된 그래프
3) 간선이 제거되면 연결이 끊어지는 연결 그래프
4) 꼭짓점보다 변의 개수가 1개 적은 그래프
나무의 예:
충분히 발달된 가계도가 나무를 형성합니다. 특정(잘 알려진) 개인으로 시작하여 각 부모와 각 아들이나 딸 사이에 가장자리를 그리면 트리가 형성됩니다. 그러나 가계도를 작성할 때에는 먼 친척 간의 결혼이 순환을 형성하지 않도록 세심한 주의를 기울여야 합니다.
그래프의 속성
정리 4.2(1).
그래프의 꼭지점의 차수의 합은 항상 짝수입니다.
증거
그래프의 각 모서리에는 두 개의 끝이 있으므로 각 끝의 차수는 하나의 모서리를 희생하여 1만큼 증가합니다. 따라서 각 모서리는 모든 꼭지점의 각도 합계에 2단위를 기여하므로 합계는 모서리 수의 두 배가 되어야 합니다. 따라서 합은 짝수이다.
정리 4.2.(2)
모든 그래프에서 홀수차 꼭지점의 개수는 짝수입니다.
증거
우리는 모순에 의해 증명을 수행할 것입니다. 정리가 참이 아니라고 가정하면 정리가 참이라는 결론을 내리는 모순을 찾을 것입니다. 정리가 참이 아니면, 차수가 홀수인 꼭지점의 개수가 홀수입니다. 그러나 짝수인 정점의 차수의 합은 짝수입니다. 모든 꼭지점의 차수 합은 홀수 차수를 갖는 꼭지점의 차수 합과 짝수 차수를 갖는 꼭지점의 차수 합을 더한 것입니다. 홀수와 짝수의 합은 홀수이므로 모든 꼭지점의 차수의 합은 홀수입니다. 그러나 이는 정리 4.1(1)과 모순되므로 모순에 도달했습니다. 그러므로 우리는 정리가 참이라는 결론을 내립니다.
예제 4.2.(1)
7개 팀이 축구 토너먼트를 조직하여 각 팀이 정확히 3경기를 치르는 것이 가능합니까?
아니요, 7개의 꼭지점으로 그래프를 만들고 각 꼭지점에서 3개의 간선을 도출하려고 하면 되기 때문입니다. 정리 4.2(2)에 따르면 이러한 그래프를 구성하는 것은 불가능합니다.
정의 4.2(1).
동일한 구조를 갖는 그래프를 동형(isomorphic)이라고 합니다. 인접성을 유지하는 정점 세트 사이에 일대일 대응이 있는 경우 두 그래프 G와 H는 동형입니다(때로는 G=H로 표시됨). 예를 들어, 그림의 G와 H는 다음과 같습니다. 4. 2(2)는 대응 하에서 동형입니다.
즉, 이러한 그래프 각각의 정점은 정점이 두 번째 그래프에서 이웃하는 경우에만 정점이 이웃하는 방식으로 정점에 번호가 매겨질 수 있는 방식으로 번호가 매겨질 수 있습니다.
동형은 그래프의 등가 관계입니다.
정의 4.2(2)
그래프라고 합니다 일관성 있는, 두 정점 사이에 경로가 있는 경우.
연결 구성 요소– 자체적으로 연결되어 있지만 연결된 상태를 유지하도록 확장할 수 없는 그래프의 일부
그래프 G의 연결성 x=x(G)는 제거 시 연결이 끊어지거나 사소한 그래프로 이어지는 정점의 최소 수입니다. 정의에 따르면 연결이 끊긴 그래프의 연결성은 0과 같고, 연결점이 있는 연결된 그래프의 연결성은 1과 같습니다. 그래프에서 몇 개의 꼭지점을 제거하더라도 완전한 그래프를 연결 해제할 수는 없습니다. 그것.
그래프
그래프는 18세기 유명한 수학자 레온하르트 오일러(Leonhard Euler)가 현재 고전적인 쾨니히스베르크 교량 문제를 해결하려고 시도하면서 시작되었습니다. 당시 Konigsberg시에서 그림에서 볼 수 있듯이 프레골 강 유역과 서로 7개의 다리로 연결된 두 개의 섬이 있었습니다. 7.1. 임무는 다음과 같습니다. 각 다리를 정확히 한 번만 걸은 후 걷기가 시작된 동일한 장소로 돌아가는 방식으로 도시를 산책하는 것입니다. 이 문제를 해결하기 위해 오일러는 Koenigsberg를 그래프로 묘사하여 정점을 도시의 일부로 식별하고 가장자리를 이러한 부분을 연결하는 다리로 식별했습니다. § 7.1에서 볼 수 있듯이 오일러는 원하는 도시 주변 경로가 존재하지 않는다는 것을 증명할 수 있었습니다.
그림 7.1. 오래된 Koenigsberg의 계획
이 장에서는 그래프 이론에서 사용되는 표준 용어를 소개하고 그래프를 사용하여 해결할 수 있는 몇 가지 구체적인 문제를 검토합니다. 특히, 트리라고 불리는 그래프 클래스를 소개하겠습니다. 트리는 계층적 시스템으로 구성된 데이터를 나타내는 자연스러운 모델입니다. 개별 항목을 분리하기 위한 트리 검색과 트리의 데이터 정렬은 컴퓨터 과학에서 중요한 노력 포인트입니다. 이 장의 부록에서는 트리로 정리된 데이터를 정렬하고 검색하는 방법을 살펴보겠습니다.
그래프 및 용어
그림에서. 7.1은 쾨니히스베르크(Königsberg)의 7개 다리를 이렇게 보여줍니다. 18세기에 그들이 어떻게 위치했는지. 오일러가 해결한 문제는 다음과 같습니다. 각 다리를 정확히 한 번 지나고 도시의 같은 장소에서 시작하고 끝나는 도보 경로를 찾을 수 있습니까?
작업 모델은 다음과 같습니다. 그래프,다수로 이루어진 봉우리그리고 많은 갈비 살정점을 연결합니다. 정점 A, B, C 및 디 강둑과 섬, 갈비뼈를 상징합니다. a,c, 기음,디,에프 그리고 g 7개의 다리를 나타냅니다(그림 7.2 참조). 필요한 경로(존재하는 경우)는 각 가장자리를 한 번만 횡단하는 방식으로 그래프의 가장자리를 횡단하는 것과 같습니다. 갈비뼈의 통과는 분명히 다리로 강을 건너는 것과 일치합니다.
그림 7.2. Königsberg 교량 문제 모델
경로가 있는 그래프, 동일한 꼭지점에서 시작하고 끝나며 그래프의 모든 모서리를 정확히 한 번만 통과하는 경로가 있는 그래프를 호출합니다. 세일러 그래프.경로 자체와 마찬가지로 원하는 경로가 통과하는 정점 시퀀스(반복 가능)를 호출합니다. 오일러리안 주기. 오일러는 그래프에 오일러 순환이 있으면 어떤 꼭지점으로 이어지는 모든 모서리에 대해 이 꼭지점 1을 떠나는 또 다른 모서리가 있어야 한다는 점을 알아차렸고, 이 간단한 관찰로부터 그는 다음과 같은 결론을 도출했습니다. 그래프가 주어지면 각 정점에는 짝수 개의 가장자리가 있어야 합니다.
또한, 오일러는 반대 진술을 증명할 수 있었습니다. 즉, 정점 쌍이 일련의 모서리로 연결된 그래프는 모든 정점의 차수가 짝수인 경우에만 오일러 그래프입니다. 도꼭지점 v 숫자 δ(v)라고 불린다 갈비뼈, 그녀 사건 2 .
이제 Königsberg 브리지 문제를 모델링하는 그래프에서 오일러 사이클을 찾을 수 없다는 것이 매우 분명해졌습니다. 실제로 모든 정점의 각도는 홀수입니다. δ(비) = δ(C)= δ(D) = 3 및 δ(에이) = 5. 오일러의 도움으로 우리가 교량 문제를 풀 때 연구한 것과 유사한 그래프가 많은 실제 문제를 해결하는 데 사용되기 시작했고, 그들의 연구는 수학의 중요한 영역으로 성장했습니다.
간단한 그래프 G = (V, 이자형),여기서 V는 정점의 유한 집합이고, 이자형- 유한한 모서리 세트이며 포함할 수 없습니다. 루프(동일한 꼭지점에서 시작하고 끝나는 모서리) 및 다중 모서리(다중 가장자리는 동일한 정점 쌍을 연결하는 여러 가장자리입니다). 그림에 표시된 그래프. 7.2. 예를 들어 정점이 있기 때문에 간단하지 않습니다. 에이그리고 안에두 개의 모서리로 연결됩니다(이 모서리를 다중이라고 함).
두 개의 봉우리 유 그리고 다섯간단한 그래프에서는 인접한, 어떤 가장자리로 연결되어 있는 경우 이자형, 그들은 그것이라고 말합니다 부대꼭짓점 u (그리고 v ). 따라서 우리는 많은 것을 상상할 수 있습니다 이자형모서리는 인접한 정점 쌍의 집합으로, 집합에 대한 비반사 대칭 관계를 정의합니다. 다섯.반사성이 부족한 이유는 단순한 그래프에 루프, 즉 양쪽 끝이 동일한 꼭지점에 있는 모서리가 없기 때문입니다. 관계의 대칭성은 가장자리가 이자형, 꼭지점 연결 그리고와 함께 다섯,연결하고 다섯와 함께 그리고(즉, 가장자리에는 방향이 없습니다. 즉, 방향이 없습니다.) 한 쌍의 정점을 연결하는 간단한 그래프의 단일 간선 유 그리고 다섯,우리는 그것을 다음과 같이 표시할 것이다. andv(또는 vi).
그래프의 꼭지점 집합에 대한 관계의 논리 행렬은 모서리로 정의됩니다. ,인접 행렬.인접 행렬 M의 관점에서 관계의 대칭성은 M이 다음을 의미합니다. 주 대각선에 대해 대칭입니다. 그리고 행렬 M의 주대각선에 대한 이 관계의 비반사성으로 인해 "L" 기호가 있습니다.
예제 7.1. 그래프 G(V, E) 그리기 정점 집합 V = (a, b, c, d, e) 및 모서리 세트 E = (ab, ae, bc, bd, ce, de). 인접 행렬을 적어보세요.
해결책. 그래프 G는 그림 1에 나와 있습니다. 7.3.
그림 7.3.
인접 행렬의 형식은 다음과 같습니다.
그래프를 복원하려면 주대각선 위에 있는 인접 행렬 요소만 필요합니다.
하위 그래프그래프 G = (V, E)는 E' C E 및 V' C V인 그래프 G' = (V', E')라고 합니다.
예제 7.2그림에 표시된 그래프 H, K, L 중에서 찾아보세요. 7.4, 그래프 G의 하위 그래프.
해결책.그림 1과 같이 그래프 G, H, K의 꼭지점을 표시해 보겠습니다. 7.5. 그래프 H와 K는 표기법에서 볼 수 있듯이 G의 하위 그래프입니다. 그래프 L은 인덱스가 4인 꼭지점을 가지지만 G는 그렇지 않기 때문에 G의 하위 그래프가 아닙니다.
노선길이 케이 그래프 G에서 이러한 꼭지점 시퀀스를 호출합니다. 다섯 0 , 다섯 1 , …, 다섯 케이 , 각 i = 1, …, k 쌍에 대해 다섯 나 – 1 다섯 나 그래프의 가장자리를 형성합니다. 우리는 그러한 경로를 다음과 같이 표시할 것입니다. 다섯 0 다섯 1 … 다섯 케이 . 예를 들어, 1 4 3 2 5는 예제 7.2의 그래프 G에서 길이가 4인 경로입니다.
G
시간
케이 엘
그림 7.4.
주기그래프에서는 정점 시퀀스를 호출하는 것이 일반적입니다. 다섯 0 , 다섯 1 , … , 다섯 케이 , 각 쌍은 한쪽 가장자리의 끝이며, 다섯 0 = 다섯 1 , 나머지 정점(및 가장자리)은 반복되지 않습니다. 즉, 순환은 각 정점과 가장자리를 한 번만 통과하는 닫힌 경로입니다.
1
2 1 2
3
그림 7.5
예제 7.3.예제 7.2의 그래프 G에서 순환을 찾으십시오.
해결책.이 그래프에는 길이가 5인 두 가지 다른 주기가 있습니다.
1 3 2 5 4 1 및 1 2 5 4 3 1
우리는 순환의 임의의 상단에서 시작하여 한 방향 또는 다른 방향으로 이러한 순환을 진행할 수 있습니다. 또한 그래프에는 길이가 4인 세 가지 다른 주기가 있습니다.
1 2 5 4 1, 1 2 3 4 1 및 2 5 4 3 2,
길이가 3인 두 개의 루프:
1 2 3 1 및 1 3 4 1.
순환이 없는 그래프를 호출한다. 비순환적.계산 시 발생하는 트리 구조는 비순환 그래프의 특별한 경우입니다. 이 장의 뒷부분에서 이에 대해 다루겠습니다.
백작, 전화함 일관성,정점의 쌍이 어떤 경로로 연결되어 있는 경우. 모든 일반 그래프는 하위 그래프로 나눌 수 있으며 각 하위 그래프는 연결되어 있습니다. 이러한 연결된 구성 요소의 최소 수를 호출합니다. 연결 번호그래프로 표시되며 기음(G) . 연결 문제는 그래프 이론을 컴퓨터 네트워크에 적용하는 데 중요합니다. 그래프의 연결 수를 결정하는 데는 다음 알고리즘이 사용됩니다.
연결 알고리즘.
G = (V, E)를 그래프로 둡니다. 알고리즘은 값을 계산하도록 설계되었습니다. 기음 = 기음(G), 저것들. 주어진 그래프 G의 연결된 구성 요소 수.
V' :=V;
~하는 동안V'≠ ø하다
y Є를 선택하세요. 다섯’
경로를 y에 연결하는 정점을 찾으세요.
정점 제거다섯' 그리고
E의 해당 가장자리;
기음:= 기음+1;
예제 7.4.그림 1의 그래프에서 연결성 알고리즘의 작동을 관찰하십시오. 7.6.
그림 7.6.
해결책.표를 참조하세요. 7.1.
표 7.1.
|
초기값 |
{1,2,3,4,5,6,7,8} |
|
|
선택 y = 1 |
||
|
선택 y = 2 |
||
|
선택 y = 7 |
그래서, 기음(G) = 3. 해당 연결된 구성요소는 그림 1에 표시되어 있습니다. 7.7.
5
주요 질문:
그래프 기록의 정보. 카운트 및그 요소.
그래프의 경로 및 경로
연결된 그래프. 나무
그래프 작업. 그래프 이론은
수학의 한 분야
폭넓은 실제 적용.
그래프 이론 - 분야
이산 수학,
어떤 기능이
연구에 대한 기하학적 접근
사물.
그래프의 역사
처음으로 그래프 이론의 기초레너드의 작품에 등장
오일러(1707-1783;
스위스, 독일,
러시아 수학자)
그는 해결책을 설명했습니다.
퍼즐과 수학
엔터테인먼트 작업.
그래프 이론은 다음과 같이 시작되었습니다.
오일러의 문제 해결
일곱 개의 다리
Koenigsberg. 다음 수수께끼는 Königsberg 주민들 사이에서 오랫동안 흔했습니다.
다리를 하나도 건너지 않고 (프레골리아 강 건너편) 모든 다리를 건너는 방법
그 중 두 번? 많은 사람들이 이 문제를 이론적으로나 해결하기 위해 노력해 왔습니다.
실질적으로 걷는 동안. 그러나 아무도 성공하지 못했지만
이것이 이론적으로도 불가능하다는 것을 증명하는 것이 가능했습니다.
부품의 단순화된 다이어그램에서
시(군) 교량
선에 해당합니다(호
카운트) 및 도시 일부 -
선 연결점
(그래프의 꼭지점).
그의 추론 과정에서 오일러는 다음과 같은 사실을 깨달았습니다.
다음 결론: 통과할 수 없음
어느 다리도 거치지 않고 모든 다리를 건너
두 번.
그래프의 역사
'그래프'라는 용어는 책에 처음 등장했습니다.1936년 헝가리 수학자 D. Koenig
그래프에 관한 초기의 가장 중요한 정리
L. 오일러에게 돌아가세요.
이론은 그래프의 개념을 기반으로 합니다.
- 유한수의 집합그래프의 정점이라고 불리는 점, 그리고
이들 중 일부를 쌍으로 연결
모서리라고 불리는 선의 꼭지점 또는
그래프의 호. 때로는 그래프 전체가
하나의 대문자로 표시될 수 있다
편지.
G V , X 를 2개의 쌍이라고 합니다.
유한 집합: 점 V 및
선 세트 X(모서리, 호),
몇 쌍의 점을 연결합니다.
그래프의 구성
그래프는 선으로 연결된 꼭지점으로 구성됩니다. 봉우리열은 라틴 문자 A, B, C, D 또는
숫자로.
방향이 있는 선(화살표 포함)을 호라고 합니다.
방향이 없는 선(화살표 없음)을 모서리라고 합니다.
특정 꼭지점을 떠나 다음으로 들어가는 선
이를 루프라고 합니다.
호
에이
가장자리
안에
고리
와 함께
유향 그래프 -
정점이 호로 연결된 그래프. 와 함께그러한 그래프를 이용하여 표현할 수 있다.
단방향 관계 체계.
유라
안야
마샤
콜야
비티야
가중치 그래프
모서리나 호가 할당된 그래프입니다.숫자 값에 해당합니다(그들은
예를 들어 도시 사이의 거리를 나타냅니다.
또는 교통비).
그래프의 가중치는 간선의 가중치의 합과 같습니다.
4
비
기음
2
3
2
에이
1
이자형
디
에이
비
기음
디
이자형
ABCDE
3 1
4
2
3 4
2
1
2 2
테이블(중량 테이블이라고 함)
행렬)은 그래프에 해당합니다. 만약에
그래프 G의 모서리는 두 그래프를 연결합니다.
정점 V와 W(예: V ,W X), 그러면 그들은 다음과 같이 말합니다.
이 가장자리는 그들에게 부수적이라는 것입니다.
그래프의 두 꼭지점을 인접이라고 합니다.
가장자리에 사건이 있는 경우: 켜짐
그림에서 정점 A와 B는 서로 인접해 있습니다.
A와 S.
에이
와 함께
안에 그래프 G에 원점이 있는 간선이 있는 경우
끝이 일치하면 이 가장자리를 호출합니다.
고리. 그림에서 모서리 q(C, C)는 루프입니다.
큐
이자형
와 함께
에이
디
비 두 간선이 인접해 있으면 인접하다고 합니다.
공통 꼭지점을 가지고 있습니다.
그림에서 인접한 것은 예를 들어 다음과 같습니다.
공통 정점 C를 갖는 가장자리 x1 및 x2.
디
x5
x1
에프
와 함께
x4
x2
G
x7
x3
이자형
x6
비
시간
에이 하나로 시작하는 갈비뼈와
같은 정점, 같은 방식으로 끝나다
같은 꼭지점에서 호출됩니다.
다중 또는 병렬.
유형의 동일한 쌍 수
(V , W)를 모서리의 다중성(V , W)이라고 합니다.
꼭지점 A에 입사하는 모서리의 수는 다음과 같습니다.
이 꼭지점의 차수라고 하며
deg(A)로 표시됩니다(영어 학위 –
도). 그림에서 배수는 예를 들어 다음과 같습니다.
가장자리 x1(A, B), x2(A, B). 정점 A와 C
모서리 x3, x4, x5가 입사됩니다. 따라서,
edge AC는 다중도가 3이고 edge
AB – 다중성은 2와 같습니다.
에이
x4
x1
x3
와 함께
x2
x5
안에 그림에서 정점 A는 차수를 갖습니다.
1, 정점 C – 4, 정점 D – 2와 같습니다.
이는 deg(A)=1, deg(C)=4 형식으로 작성됩니다.
각도(D)=2.
디
x5
x1
에프
와 함께
x4
x2
G
x7
x3
이자형
x6
비
시간
에이 차수가 0인 그래프의 꼭짓점은 다음과 같습니다.
절연이라고 합니다.
분리된 꼭짓점으로 구성된 그래프
널 그래프(null graph)라고 합니다.
차수가 1인 그래프의 꼭지점
교수형이라고.
간선(호)이 없는 그래프를 호출합니다.
비어 있는.
이자형
기음
에이
디
비
사진에서 위쪽은
E – 격리됨:
각도(E)=0. 그림에서 정점 A, B, E, G, H는 펜던트입니다.
디
x5
x1
에프
와 함께
x4
x2
G
x7
x3
이자형
x6
비
시간
에이 정리 1. 그래프 G V 에서 X 의 합
모든 정점의 차수는 짝수입니다.
그래프 모서리 수의 두 배와 같습니다.
N
각도(V) 2m
나는 1
나
모든 그래프의 간선 수는 다음과 같습니다.
정점 각도의 합의 절반입니다.
여기서 n V
- 정점 수;
m X는 그래프의 모서리 수입니다. 꼭짓점을 짝수(odd)라고 합니다.
그 차수가 짝수(홀수)인 경우.
그림에서 deg(D)=2, deg(F)=3, 즉
그래프 정점 D는 짝수이고 F는
이상한.
x5
디
x1
에프
와 함께
x4
x2
G
x7
x3
이자형
x6
비
시간
에이
일. Malenky 마을에는 15개의 전화기가 있습니다. 각 전화기가 정확히 5개의 전화기에 연결되도록 전선으로 연결할 수 있습니까?
다른 사람들? 정리 2. 임의(비지향)그래프에는 짝수 개의 홀수가 포함되어 있습니다.
봉우리
결과. 그래프를 그리는 것은 불가능하다.
홀수 개의 홀수 정점.
그래프 G를 완전이라 부른다.
둘 중 하나라도 다르다면
정점은 하나로 연결되고
단 하나의 가장자리.
일. 수업에는 30 명이 있습니다. 9명에게는 3명의 친구가 있고, 11명은 4명의 친구가 있고, 10명은 5명의 친구가 있을 수 있습니까?
그래프 G V , X의 보수는 다음과 같습니다.그래프 G V , X 와 동일한 꼭지점 V
그래프 G, 그리고 오직 그 변들 X만 가지고,
그래프 G에 추가해야 합니다.
가득 차게 되었습니다. 그림에서 그래프 G1을 추가하여
그래프 G는 그래프이다
G1
G
G1
G1 패턴 1.
패턴 2.
꼭지점 각도
학위의 합
완전한 그래프
동일하며,
각각은 1이다
적은 수
이것의 꼭대기
그래프
그래프 정점 번호
균등하다, 동등하다
숫자를 두 배로 늘리다
그래프의 가장자리. 이것
무늬
공평하지 않다
완전한 경우에만
하지만 누구에게도
그래프. 패턴 3.
패턴 4.
홀수
불가능한
어떤 정점
열은 짝수입니다.
으로 그래프를 그리다
기수
이상한 정점. 패턴 5.
패턴 6.
모든 정점이 있는 경우
모든 것을 담은 그래프
열이 짝수이면
찢어지지 않고 가능해요
종이 연필
(“한 번의 스트로크로”),
각각 스와이프해서
갈비뼈는 한 번만,
이 그래프를 그려보세요.
이동이 가능합니다
무엇이든 시작하세요
탑과 마무리
그 사람은 같은 정점에 있어.
이상한 두 개
피크, 당신은 할 수 있습니다
그리지 말고
연필을 찢다
종이에서, 그 동안
움직임이 필요하다
중 하나로 시작
이 이상한
탑과 마무리
그 중 두 번째. 패턴 7.
더 많은 그래프
이상한 두 개
최고점, 불가능
"하나를 그려라
번창으로." 수치
(그래프)
들어올리지 않고 그리다
종이 연필,
~라고 불리는
유니버셜.
그래프의 경로 및 경로
유방향 그래프의 경로를 호출합니다.최종 호의 순서
마지막 호가 아닌 호의 꼭지점,
다음 호의 시작 정점입니다.
경로가 놓인 봉우리,
길의 시작이라고 불리는 곳은 꼭대기가 끝이다
경로 - 경로의 끝입니다.
각 정점이 사용되는 경로
한 번만, 단순이라고 함
방법.
그래프의 경로 길이는 호의 수입니다.
(가장자리)가 이 경로를 구성합니다. 예를 들어, 이중 그래프를 고려하십시오
그림에 제시되어 있습니다. 기존 중 하나
정점 1과 3을 연결하는 경로는 다음과 같습니다.
꼭지점 순서 1, 2, 1, 4, 3. 유일한 것
동일한 정점 쌍에 대한 간단한 경로는 다음과 같습니다.
시퀀스 1, 4, 3. 정점 1에서 다음으로의 경로
동일한 그래프에 정점 5가 존재하지 않습니다. 방향이 없는 그래프를 호출합니다.
경로가 하나 이상 있으면 연결됨
각 정점 쌍 사이.
연결되어 있으면 이중 그래프를 연결됨이라고 합니다.
방향이 없는 그래프
원래 지향에서 얻은 것입니다.
모든 호를 가장자리로 대체합니다. 다음과 같은 경우 경로를 닫힌 경로라고 합니다.
시작 꼭지점과 끝 꼭지점은 동일합니다.
닫힌 경로를 사이클이라고 합니다.
정점(초기 및 최종 정점 제외)
다르다.
그래프를 고려하십시오. 그에게 길은 2, 1, 6, 5, 4, 1,
2는 닫혀 있습니다. 경로는 1, 6, 5, 4, 1입니다.
주기이다. 쌍별 인접 시퀀스
무방향 그래프의 정점, 즉
모서리의 순서
두 번째 무향 그래프
이전 모서리의 꼭지점이 다음과 일치합니다.
다음 정점의 첫 번째 정점을 호출합니다.
노선.
경로의 모서리 수를 길이라고 합니다.
노선.
경로의 시작 정점이 일치하는 경우
마지막 경로를 사용하면 그러한 경로가 호출됩니다.
폐쇄 또는 루프. 그림에서 HCDFD는 길이가 4인 경로입니다.
명칭: |HCDFD|=4. 허용되는 경로
묻다
어떻게
후속
갈비 살,
여러 개가 있을 때 편리하기 때문에
갈비 살
엑스
디
x1
5
에프
와 함께
x4
x2
G
x7
x3
이자형
x6
비
시간
에이 그림의 그래프에서 (t, s, p, r), (u, s, t, r)은 사이클
길이 4, (r, t, q, s, u) – 주기 길이 5, (t, s, u, r, t, s, p, r)
– 8주기, (p, u) – 2주기, 루프 (q) – 1주기.
이자형
큐
기음
에스
에이
피
티
디
아르 자형
비
유
그래프 작업
단일 작업1. 그래프의 모서리 제거 - 이 경우 그래프의 모든 정점을 제거합니다.
저장되었습니다
2. 둘 사이에 그래프 가장자리 추가
기존 피크.
3. 정점 삭제(인시던트와 함께)
갈비 살).
4. 정점 추가(연결될 수 있음)
그래프의 일부 꼭지점).
5. 모서리의 수축 - 한 쌍의 꼭지점 식별, 즉
인접한 정점 쌍을 제거하고 새 정점 추가
정점에 인접한 정점
원격 정점 중 적어도 하나에 인접)
6. 가장자리 세분화 - 가장자리 제거 및 추가
각각의 모서리에 의해 연결된 새로운 정점
원격 가장자리의 정점.
그래프 작업
이중 작업그래프 G1(V1, X 1)과 G2(V2, X 2)를 결합하여
정점 집합인 그래프 G G1 G2 라고 합니다.
이는 V V1 V2 이고 간선 세트는 X X 1 X 2 입니다.
그래프 G1과 G2의 교차점을
그래프 G G1 G2에서 X X 1 X 2는 모서리 집합이고 V V1 V2는 정점 집합입니다.
두 그래프의 링 합을 그래프라고 합니다.
G G1 G2는 정점 세트에 의해 생성됨
저것들.
V V1 V2 및 모서리 세트 (X1 X 2) \ (X1 X 2) ,
G1 또는 G1에 포함된 모서리 세트
G2이지만 G1 G2에는 없습니다. V4
V2
x3
x2
V3
x4
V1
x1
V5
x2
x7
x3
x4
x4
V1
x7
V1
G=G1UG2
V3
x4
V5
x2
V1
x3
G=G1∩G2
V2
x1
G2
V4
V2
x5 x6
x6
V3
V1
V4
V3
V4
x5
x3
x1
G1
V2
V5
V2
V4
x5 x6V
3
x7
G=G1 G2
그래프의 응용
와 함께도움을 받아
그래프
쉽게 한
수학 문제, 퍼즐,
독창성.
해결책
작업
더 나아가
그래프의 응용
미로는 그래프이다. 그리고 그것을 탐구하는 것은 그것을 찾는 것이다이 그래프의 경로입니다.
더 나아가 그래프를 사용하고
귀족.
그림은 보여줍니다
족보의 일부
나무
유명한
고귀한 가족 L.N.
톨스토이. 여기 있어요
정점은 이것의 멤버입니다
친절하고, 그들을 연결해주는 사람들
세그먼트 - 관계
혈연 관계,
부모로부터 이어지는
어린이들.
더 나아가
그래프의 응용
그래프는 프로그램의 블록 다이어그램입니다.컴퓨터.
더 나아가
그래프의 응용
일반적인 그래프지리적 지도는
철도 이미지.
더 나아가
그래프의 응용
도시 지도의 일반적인 그래프도시 교통 패턴입니다
수송.
더 나아가
결론
그래프는 훌륭한 수학적 도구입니다당신이 해결할 수 있는 객체
수학적, 경제적, 논리적
작업. 다양한 해결도 가능해요
퍼즐을 풀고 작업 조건을 단순화합니다.
물리학, 화학, 전자, 자동화. 그래프
사용된다
~에
작성
카트
그리고
계보 나무.
수학에도 특별과목이 있어요
이를 "그래프 이론"이라고 합니다.
콘텐츠
완전히 연결이 끊긴 그래프 . 많은 간선이 비어 있는 그래프를 호출합니다. 꽤 일관되지 않은(또는 비어 있음) 그래프.우리는 n개의 꼭지점을 갖는 완전히 연결이 끊긴 그래프를 Nn으로 표시할 것입니다. N4는 도 1에 도시되어 있다. 1. 참고하세요 ~에완전히 연결이 끊긴 그래프에서는 모든 정점이 격리됩니다. 완전히 연결이 끊긴 그래프는 특별한 관심 대상이 아닙니다.
완전한 그래프 . 임의의 두 정점이 인접한 간단한 그래프를 완전한 그래프. n개의 정점을 가진 완전한 그래프는 일반적으로 다음과 같이 표시됩니다. 그래프는 그림 1에 나와 있습니다. 2와 3은 정확히 n(n - 1)/2개의 모서리를 가집니다.
일반 그래프 . 모든 정점의 차수가 동일한 그래프를 호출합니다. 일반 그래프.각 정점의 차수가 r이면 그래프가 호출됩니다. 정규 학위 r. 3차 정규 그래프라고도 함 큐빅(또는 3가)그래프(예를 들어 그림 2 및 4 참조) 큐빅 그래프의 또 다른 유명한 예는 소위 피터슨 백작,그림에 표시됩니다. 5. 완전히 연결되지 않은 모든 그래프는 0차의 정규 그래프이고, 모든 완전한 그래프 Kn은 n - 1차의 정규 그래프입니다.
플라톤 그래프 . 정사면체, 정육면체, 정팔면체, 정십이면체, 정이십면체 등 5개의 정다면체의 꼭지점과 모서리로 형성된 소위 플라톤 그래프가 특히 흥미롭습니다. 그래프는 사면체에 해당합니다(그림 2). 정육면체와 팔면체에 해당하는 그래프가 그림 1에 나와 있습니다. 5 및 6;
이분 그래프 . 그래프의 꼭지점 집합이 두 개의 분리된 부분 집합 V 1 과 V 2 로 분할되어 G의 각 모서리가 V 1의 일부 꼭지점과 V 2의 일부 꼭지점을 연결한다고 가정합니다(그림 7).
G를 이분 그래프(bipartite graph)라고 합니다. 지정된 두 하위 집합을 구별하려는 경우 이러한 그래프는 때때로 G(V 1, V 2)로 표시됩니다. 이분 그래프는 정점을 빨간색과 파란색이라는 두 가지 색상으로 색칠하는 등 다른 방식으로 정의할 수도 있습니다. 그래프의 각 정점이 빨간색이나 파란색으로 칠해져 모든 가장자리의 한쪽 끝은 빨간색이고 다른 쪽 끝은 파란색인 경우 그래프를 이분형 그래프라고 합니다. 이분 그래프에서는 V 1 의 모든 정점이 V 2 의 모든 정점에 연결될 필요는 없다는 점을 강조해야 합니다. 이것이 사실이고 그래프 G가 단순하면 다음과 같이 호출됩니다. 완전한 이분 그래프일반적으로 m, n은 각각 V 1 및 V 2의 정점 수로 표시됩니다. 예를 들어, 그림. 도 8은 그래프 K 4, 3을 도시한다. 그래프에는 정확히 m + n개의 정점과 mn개의 모서리가 있습니다. 이 형식의 완전한 이분 그래프를 별 그래프라고 합니다. 그림에서 도 9는 별 그래프를 도시한다.
연결된 그래프 . 그래프 연결됨,두 그래프의 합집합으로 표현할 수 없는 경우 일관되지 않은그렇지 않으면. 분명히 모든 연결되지 않은 그래프 G는 유한한 수의 연결된 그래프의 합집합으로 표현될 수 있습니다. 이러한 연결된 각 그래프를 호출합니다. 구성요소(연결)그래프 G. (그림 10은 세 가지 구성 요소가 있는 그래프를 보여줍니다.) 연결된 그래프에 대해 먼저 임의 그래프에 대한 특정 설명을 증명한 다음 이를 각 구성 요소에 개별적으로 적용하는 것이 편리한 경우가 많습니다.
"격리된" 꼭짓점으로 구성된 그래프 다이어그램을 호출합니다. 제로 그래프. (그림 2)
가능한 모든 간선이 구성되지 않은 그래프를 호출합니다. 불완전한 그래프. (그림 3)
가능한 모든 간선이 구성된 그래프를 호출합니다. 완전한 그래프. (그림 4)
그래프의 모서리에 모서리의 방향을 나타내는 화살표가 있는 경우 해당 그래프를 호출합니다. 감독.
그림에 표시된 그래프에서 한 작업에서 다른 작업으로의 화살표는 작업 순서를 의미합니다.
기초 공사를 마치지 않고는 벽 설치를 시작할 수 없습니다. 마무리를 시작하려면 바닥에 물이 있어야 합니다.
꼭지점의 각도와 가장자리의 수를 계산합니다.
그래프의 꼭지점을 떠나는 간선의 수를 꼭지점의 차수라고 합니다. 그래프에서 차수가 홀수인 꼭지점을 홀수, 짝수인 꼭지점을 짝수라고 합니다.그래프의 모든 꼭지점의 차수가 동일한 경우 그래프를 호출합니다. 질의. 따라서 모든 완전한 그래프는 동질적입니다.
그림 5는 5개의 정점이 있는 그래프를 보여줍니다.
정점 A의 정도를 St.A로 표시합니다.
그림에서:
St.A = 1, St.B = 2, St.B = 3, St.G = 2, St.D = 0.
특정 그래프에 내재된 몇 가지 규칙성을 공식화해 보겠습니다.
패턴 1.완전한 그래프의 꼭짓점의 차수는 동일하며, 각각의 꼭짓점 수는 이 그래프의 꼭짓점 수보다 1이 적습니다.
패턴 2.그래프의 꼭지점 각도의 합은 그래프 모서리 개수의 2배에 해당하는 짝수입니다.
이 패턴은 전체 그래프뿐만 아니라 모든 그래프에도 적용됩니다.
모든 그래프에서 홀수 꼭지점의 개수는 짝수입니다..
완전한 그래프에 n개의 정점이 있는 경우 간선의 수는 n(n-1)/2와 같습니다.
완성되지 않은 그래프는 누락된 간선을 추가하여 동일한 정점으로 완성될 수 있습니다. 예를 들어, 그림 3은 5개의 정점이 있는 불완전한 그래프를 보여줍니다. 그림 4에서는 그래프를 완전한 그래프로 변환하는 모서리를 다른 색상으로 표시합니다. 이러한 모서리가 있는 그래프의 꼭지점 모음을 그래프의 보수라고 합니다.
오일러 그래프.
종이에서 연필을 떼지 않고도 그릴 수 있는 그래프를 그래프라고 합니다. 오일러리안. (그림 6)
이 그래프는 과학자의 이름을 따서 명명되었습니다. 레온하르트 오일러.
패턴 3.(우리가 고려한 정리를 따릅니다).
홀수 개의 꼭지점을 갖는 그래프를 그리는 것은 불가능합니다.
패턴 4.그래프의 모든 정점이 균등한 경우 종이에서 연필을 떼지 않고도("한 획으로") 각 가장자리를 따라 한 번만 이동하여 이 그래프를 그릴 수 있습니다. 움직임은 모든 정점에서 시작하여 동일한 정점에서 끝날 수 있습니다.
패턴 5.두 개의 홀수 꼭지점만 있는 그래프는 종이에서 연필을 떼지 않고도 그릴 수 있으며, 움직임은 홀수 꼭지점 중 하나에서 시작하여 두 번째 꼭지점에서 끝나야 합니다.
패턴 6.홀수 꼭짓점이 2개 이상인 그래프는 그릴 수 없습니다." 한 번의 스트로크로».
종이에서 연필을 떼지 않고도 그릴 수 있는 도형(그래프)을 '그래프'라고 합니다. 단교적인.
그래프라고 합니다 일관성 있는, 정점 중 두 개가 경로, 즉 일련의 가장자리로 연결될 수 있는 경우 각 정점은 이전 정점의 끝에서 시작됩니다.
그림 7은 확실히 연결이 끊긴 그래프를 보여줍니다.
그래프라고 합니다 일관되지 않은, 이 조건이 충족되지 않으면.
예를 들어 그림에서 정점 D와 E 사이에 모서리를 그리면 그래프가 연결됩니다.( 그림 8)
그래프 이론에서는 이러한 가장자리(제거한 후 그래프가 연결에서 연결 해제로 바뀌는)를 호출합니다. 다리.
교량의 예 그림 7 DE, A3, VZh 등의 가장자리가 사용될 수 있으며, 각 가장자리는 그래프의 "격리된" 부분의 꼭지점을 연결합니다. ( 그림 8)
연결이 끊긴 그래프는 여러 개의 " 조각들" 이러한 "조각"을 그래프의 연결된 구성요소라고 합니다. 물론 연결된 각 구성 요소는 연결된 그래프입니다. 연결된 그래프에는 하나의 연결된 구성 요소가 있습니다.
그래프는 연결되어 있고 최대 2개의 홀수 정점을 갖는 경우에만 오일러 그래프입니다.
나무.
나무순환이 없는 연결된 그래프가 호출됩니다.
주기시작과 끝이 일치하는 길이다.
순환의 모든 정점이 다른 경우 이러한 순환을 호출합니다. 초등학교(또는 간단한) 주기.
사이클이 그래프의 모든 간선을 한 번 포함하는 경우 이러한 사이클을 호출합니다. 오일러선 (그림 9a).
칼럼에서는 그림 9b두 사이클: 1-2-3-4-1 및 5-6-7-5.
에 의해한 정점에서 다른 정점으로의 그래프에는 이러한 정점 사이에 경로가 놓일 수 있는 일련의 가장자리가 있습니다.
이 경우 경로의 가장자리가 두 번 이상 나타나서는 안 됩니다. 경로가 놓인 봉우리를 봉우리라고합니다. 여행의 시작, 경로 끝의 봉우리 - 길 끝.
거는 정상는 정확히 하나의 모서리가 나오는 정점입니다( 그림 10).
(매달린 봉우리는 원으로 표시됩니다).
각 트리 정점 쌍에는 이를 연결하는 고유한 경로가 있습니다..
이 속성은 가계도 형태로 가계도가 표시되는 사람의 남성 계보와 같이 가계도에서 모든 조상을 찾을 때 사용됩니다. 나무"그리고 그래프 이론의 의미에서요.
나무의 모든 가장자리는 다리입니다.
실제로, 나무의 가장자리를 제거한 후에는 " 분해하다"두 그루의 나무에.
임의의 두 정점이 정확히 하나의 단순 경로로 연결된 그래프는 다음과 같습니다. 나무.
(걸이 상단에 대해). 모든 나무에는 매달린 꼭대기가 있습니다.
. 트리에서는 꼭짓점의 개수가 변의 개수보다 하나 더 많습니다.
동형. 평면 그래프와 오일러의 정리.
두 그래프를 호출합니다. 동형의, 동일한 수의 꼭지점을 갖고 각 그래프의 꼭지점에 1부터 n까지 번호를 매길 수 있으므로 첫 번째 그래프의 꼭지점은 두 번째 그래프의 해당 꼭지점이 다음과 같이 연결된 경우에만 간선으로 연결됩니다. 가장자리.
그림 11에 표시된 그래프가 동형임을 증명해 보겠습니다. 
첫 번째와 두 번째 그래프의 정점에 1부터 4까지 번호를 매기자( 그림 12).
첫 번째 그래프는 정점 1과 2, 2와 3, 3과 4, 1과 4, 1과 3, 2와 4를 연결합니다. 두 번째 그래프에서는 정점 1과 2, 2와 3, 3과 4, 1과 4, 1과 3, 2와 4도 연결되어 있으므로 이 그래프는 동형입니다.
두 그래프가 동형인지 확인하려면 다음 사항을 확인해야 합니다.
- 같은 수의 정점
- 한 그래프의 정점이 간선으로 연결되면 다른 그래프의 해당 정점도 간선으로 연결됩니다.
변이 꼭짓점을 제외한 어느 곳에서도 교차하지 않도록 그릴 수 있는 그래프를 그래프라고 합니다. 평평한또는 평면의.
오일러. 올바르게 그려진 연결된 평면 그래프의 경우 V-E+F=2와 같습니다. 여기서 V는 정점 수, E는 모서리 수, F는 조각 수입니다(동등 V -E+. F=2는 보통 오일러의 공식으로 불린다.).
모든 꼭짓점이 다른 모든 꼭짓점의 간선에 연결되어 있는 그래프를 그래프라고 합니다. 완벽한.
폰트리아긴 – 쿠라토프스키. 그래프는 (위상학적 의미에서) "집 우물" 유형의 6개 정점이 있는 그래프와 5개 정점이 있는 완전한 그래프를 포함하지 않는 경우에만 평면입니다.
(주로 집과 우물에 관한 고대 문제에 사용되었으며, 그 본질은 문제의 그래프가 평평한지 여부, 그림 13)
방향성 그래프.
이전에 논의된 유형의 그래프를 사용하여 해결할 수 없는 중요한 종류의 실제 문제가 있습니다.예를 들어 도시의 도로나 광장 지도를 평면 그래프로 표현합니다. 그러나 자동차로 도시를 여행하기 위해 이 계획을 사용해야 하고 일부(또는 모든) 거리의 교통이 일방통행인 경우에는 어떻게 될까요?
그런 다음 문제의 도시 다이어그램(그래프)의 거리와 같은 가장자리에 직접 위치한 화살표가 이러한 상황을 탐색하는 데 도움이 될 수 있습니다.
모서리에 화살표가 있는 그래프를 호출합니다. 지향.
출력 정도유방향 그래프의 정점은 이 정점이 시작인 간선의 수입니다(간선의 수, " 나오는"위에서).
진입 정도방향 그래프의 정점은 이 정점이 끝인 간선의 수입니다(간선의 수, " 들어오는"맨 위로).
예, 에 그림 15방향 그래프 ABCD를 보여줍니다. 일부 정점의 진입 및 진출 각도는 다음과 같습니다.
St.in.A=2, St.out.A=1 St.in.B=2, St.out.B=0 St.in.D=1, St.out.D=3.
정점 A1에서 정점 An까지의 방향 그래프의 경로는 방향이 지정된 가장자리 A1A2, A2A3, ..., Аn-1Аn의 시퀀스입니다. 여기서 각 이전 가장자리의 끝은 다음 가장자리의 시작과 일치하고 각 가장자리는 다음에서 발생합니다. 이 시퀀스는 한 번만 수행됩니다.
~에 그림 15유향 그래프의 경로 예가 표시됩니다. 게다가 처음 두 경로는 간단합니다. 어떤 정점도 두 번 이상 포함되지 않습니다. 세 번째 방법은 간단하지 않습니다. to. 정점 G를 통해 경로 " 합격"두 배.
지시주기유향 그래프에서는 닫힌 경로(closed path)라고 합니다.
~에 그림 15지향성 사이클의 예는 마지막 두 그래프에 나와 있습니다. 그래프의 다른 경로와 마찬가지로 사이클의 길이는 이 경로의 간선 수에 따라 결정됩니다.
따라서 그림 16에서 A에서 D까지의 경로는 다를 수 있으며 길이도 다를 수 있습니다.
첫 번째 경로의 길이는 2이고 두 번째 경로의 길이는 3입니다.
세 번째는 4입니다.
두 정점 사이의 "최단 경로"의 길이를 정점 사이의 거리라고 합니다. 따라서 그림 16의 그래프에서 정점 A와 D 사이의 거리는 2입니다. 다음과 같이 작성됩니다: S(BP)=2.
유향 그래프에서 한 꼭지점에서 다른 꼭지점으로 "통과"하는 것이 불가능한 경우, 그 사이의 거리는 무한대(무한대 기호로 표시)라고 합니다. 따라서 그림 17에 표시된 그래프의 정점 B와 D 사이의 거리는 무한대입니다. S(DB) =
경제학의 방향성 그래프는 네트워크 계획, 수학(게임 이론, 집합 이론)에서 적극적으로 사용됩니다. 많은 문제, 특히 조합 문제를 해결할 때.
