다양한 활동 분야에서 그래프 이론의 적용. 그래프의 적용

그래프 이론의 시작은 만장일치로 1736년에 L. 오일러가 당시 유행했던 쾨니히스베르 교량의 문제를 풀면서 기인합니다. 그러나 이 결과는 100년 이상 동안 그래프 이론의 유일한 결과로 남아 있었습니다. 19 세기 중반에만 전기 엔지니어 G. Kirchhoff는 전기 회로 연구를 위해 나무 이론을 개발했으며 수학자 A. Cayley는 탄화수소 구조에 대한 설명과 관련하여 세 가지에 대한 열거 문제를 해결했습니다. 나무의 종류.

퍼즐과 재미있는 게임(체스 말에 관한 문제, 여왕에 관한 문제, "세계 일주", 결혼식과 하렘에 관한 문제 등)에서 태어난 그래프 이론은 이제 다음과 관련된 질문을 풀기 위한 간단하고 접근 가능하며 강력한 도구가 되었습니다. 광범위한 문제. 그래프는 말 그대로 어디에나 있습니다. 예를 들어, 그래프의 형태로 도로 다이어그램과 전기 회로, 지리학적 지도와 화합물 분자, 사람들과 사람들 그룹 간의 연결을 해석할 수 있습니다. 지난 40년 동안 그래프 이론은 수학에서 가장 빠르게 발전하는 분야 중 하나가 되었습니다. 이것은 빠르게 확장되는 응용 분야의 요구에 의해 주도됩니다. 그것은 집적 회로 및 제어 회로의 설계, 자동 장치 연구, 논리 회로, 프로그램 순서도, 경제 및 통계, 화학 및 생물학, 스케줄링 이론에 사용됩니다. 대체로 그래프 이론을 통해 수학적 방법이 과학 및 기술에 침투하고 있습니다.

이 논문에서 우리는 그래프 이론의 자체적인 문제가 아니라 학교 기하학 과목에서 어떻게 사용되는지를 고려한다.

따라서 연구 주제의 관련성은 한편으로는 다른 수준에서 거의 모든 현대 수학에 유기적으로 침투하는 그래프 및 관련 연구 방법의 인기와 다른 한편으로는 구현을 위한 통합 시스템에 기인합니다. 기하학의 과정은 개발되지 않았습니다.

이 연구의 목적은 학교 기하학 과정에서 그래프의 사용을 연구하는 것입니다.

대상은 기하학을 가르치는 과정입니다.

주제 – 교실 및 과외 활동

작업 : 1) 학교 기하학 과정에서 그래프 사용의 본질과 내용을 결정합니다.

2) 7-9학년에서 기하학 수업을 수행하기 위한 PMK를 개발합니다.

주요 주제는 기하 정리를 증명하기 위한 그래프 모델의 구성입니다.

이론적 근거:

1. 1736년에 발생한 그래프 이론(Leonhard Euler(1708-1783)은 빠르게 발전했습니다. 일상 생활그래픽 일러스트레이션, 기하학적 표현 및 기타 시각화 기법과 방법이 점점 더 많이 사용되고 있습니다.

1. 그래프 이론은 현대 수학의 다양한 영역과 그 수많은 응용 분야에서 응용 프로그램을 찾습니다(Lipatov E.P.).

2. 그래프 이론은 수학 논리, 조합 등의 수학 분야에서 사용됩니다.

작업의 이론적 의미는 다음과 같습니다.

그래프 이론의 적용 분야 식별;

기하학적 정리와 문제를 연구하기 위해 그래프 이론을 사용합니다.

작업의 실질적인 중요성은 기하 정리의 증명과 문제 해결에 그래프를 사용하는 데 있습니다.

이 작업의 결과로 다음이 만들어졌습니다.

7-9학년에서 기하학 수업을 수행하기 위한 소프트웨어 및 방법론적 복합물.

문제에 대한 해결책을 찾는 데 있어 가장 어려운 점은 입증 가능한 진술로 이어지는 일련의 논리적 결과를 설정하는 것입니다. 논리적으로 유능하게 추론하려면 이질적인 기하학적 사실을 논리적 관계로 구축하는 데 도움이 될 그러한 사고의 기술을 개발할 필요가 있습니다.

사고 문화의 기술을 개발하기 위해 학생들의 서면 연설 형식이 특별한 역할을 합니다. 서면 작업은 정리를 증명하고 문제를 해결할 때 논리적 추론에서 안정적인 기술을 형성하는 가장 중요한 활동입니다. 문제의 조건을 작성하는 형식, 계산 및 문제 증명의 합리적인 약어 및 표기법은 사고력을 기르고 기하학적 비전을 촉진합니다. 아시다시피 비전은 생각을 낳습니다. 문제가 발생합니다. 이질적인 기하학적 사실 사이에 논리적 연결을 설정하는 방법과 단일 전체 형태로 배열하는 방법입니다. 정리 증명 및 문제 해결의 진행 상황을 보기 위해 그래프 방식의 방법을 사용하면 증명을 보다 시각적으로 만들고 정리 및 문제 해결의 증명을 간단하고 정확하게 진술할 수 있습니다.

이를 위해 트리 그래프가 사용됩니다.

"트리"의 꼭짓점(정리 또는 문제의 조건 및 일련의 논리적 연결)은 정보가 포함된 직사각형으로 표시되며 화살표로 연결됩니다. 그래프 구성표의 끝 부분에는 증명할 주장이 포함됩니다. 정리를 증명하고 문제를 해결하는 설명 된 형식은 정리를 증명하고 문제를 해결하는 주요 단계를 쉽게 구별 할 수 있기 때문에 학생들에게 유용하고 편리합니다.

연구 부분.

섹션 1. 그래프 이론 출현의 역사 연구.

수학자 Leonhard Euler(1707-1783)는 그래프 이론의 창시자로 간주됩니다. 이 이론의 출현 역사는 위대한 과학자의 서신을 통해 추적할 수 있습니다. 다음은 1736년 3월 13일 상트페테르부르크에서 이탈리아 수학자이자 엔지니어인 마리노니에게 보낸 오일러의 편지에서 발췌한 라틴어 텍스트의 번역입니다.

"한 번 나에게 Konigsberg시에 위치하고 강으로 둘러싸여 있고 7개의 다리가 있는 강으로 둘러싸여 있다는 문제를 제안받았습니다. 문제는 누구든지 각 다리를 한 번만 통과하여 계속해서 우회할 수 있는지 여부입니다. 지금까지 그는 이 질문은 비록 진부하기는 하지만 기하학이나 대수학이나 조합 예술이 그 해결에 충분하지 않기 때문에 나에게 이 질문은 주목할만한 가치가 있는 것처럼 보였습니다. 많은 숙고 끝에 , 나는 이러한 종류의 모든 문제에서 그러한 회로가 임의의 수와 임의의 위치에 있는 브리지를 통해 만들어질 수 있는지 여부를 즉시 결정할 수 있는 완전히 설득력 있는 증거를 기반으로 하는 쉬운 규칙을 찾았습니다. 그것들은 다음 그림으로 나타낼 수 있습니다. 여기서 A는 섬을 나타내고 B, C 및 D는 강의 가지에 의해 서로 분리된 대륙의 일부입니다. 교량은 문자 a, b, c, d, e, f, g "로 표시됩니다.

이러한 종류의 문제를 해결하기 위해 발견한 방법에 대해 오일러는 다음과 같이 썼습니다.

"이 솔루션은 본질적으로 수학과 거의 관련이 없는 것 같습니다. 이 솔루션이 다른 사람이 아닌 수학자에게 기대되어야 하는 이유가 명확하지 않습니다. 왜냐하면 이 솔루션은 이성만으로 뒷받침되기 때문입니다. 이 해법을 찾기 위해 개입할 필요가 없고, 수학에 내재된 어떤 법칙도 필요하지 않습니다. 그래서 수학과 거의 관련이 없는 문제가 다른 사람보다 수학자에 의해 풀릴 가능성이 더 높다는 것이 어떻게 밝혀졌는지 모르겠습니다."

그렇다면 각 다리를 한 번만 통과하여 Königsberg 다리를 둘러볼 수 있습니까? 답을 찾기 위해 오일러가 마리노니에게 보낸 편지를 계속해 보겠습니다.

"문제는 이 7개의 다리를 모두 한 번만 지나갈 수 있는지 여부를 결정하는 것입니다. 제 규칙은 이 질문에 대한 다음 솔루션으로 이어집니다. 우선, 몇 개의 섹션이 있는지 살펴봐야 합니다. 다리를 통하는 것을 제외하고는 서로 다른 전환이 없는 물로 분리되어 있습니다. 이 예에는 A, B, C, D와 같은 4개의 섹션이 있습니다. 다음으로, 이 개별 섹션으로 이어지는 다리는 짝수 또는 홀수입니다.따라서 우리의 경우 5개의 브리지가 섹션 A로 연결되고 3개의 브리지가 나머지 섹션으로 연결됩니다. 문제 해결 모든 섹션에서. 하나의 이상한 그럴 수 없는 경우에도 규정된 대로 전환이 이루어질 수 있지만, 우회의 시작 부분만 홀수의 다리가 연결되는 두 섹션 중 하나에서 확실히 가져와야 합니다. 마지막으로 홀수의 다리가 이어지는 구간이 2개 이상이라면 그러한 이동은 일반적으로 불가능하며, 여기서 더 심각한 문제를 언급할 수 있다면 이 방법이 훨씬 더 유용할 수 있으며 무시해서는 안 됩니다. .

위 규칙의 근거는 같은 해 4월 3일자 L. 오일러가 친구 엘러에게 보낸 편지에서 찾을 수 있습니다. 우리는 이 편지에서 발췌한 내용을 아래에서 다시 말할 것입니다.

수학자는 홀수의 다리가 이어지는 강의 갈래 부분에 두 개 이상의 영역이 없으면 전환이 가능하다고 썼습니다. 이것을 쉽게 상상할 수 있도록 그림에서 이미 지나간 다리를 지웁니다. 오일러의 법칙에 따라 움직이기 시작하고 다리 하나를 건너서 지우면 그림은 다시 홀수 개의 다리가 연결되는 영역이 두 개 이하인 단면을 보여줍니다. 홀수 다리가있는 영역이 있으면 그 중 하나에 위치하게됩니다. 계속해서 모든 다리를 한 번 통과하도록 하겠습니다.

Koenigsberg시의 교량 역사는 현대적으로 이어집니다.

문제 호수에는 그림 2와 같이 서로 연결된 7개의 섬이 있습니다. 각 다리를 한 번만 통과할 수 있도록 보트는 여행자를 어느 섬으로 데려가야 합니까? 여행자를 A섬으로 데려갈 수 없는 이유는 무엇입니까?

해결책. 이 문제는 Königsberg 브리지 문제와 유사하므로 오일러의 법칙을 사용하여 해결합니다. 결과적으로 우리는 다음과 같은 답을 얻습니다. 보트는 여행자를 섬 E 또는 F로 데려가 각 다리를 한 번 건너뛸 수 있도록 해야 합니다. 동일한 오일러 규칙은 A 섬에서 시작하는 경우 필요한 우회가 불가능함을 의미합니다.

나중에 Koenig(1774-1833), Hamilton(1805-1865)은 현대 수학자 K. Berzh, O. Ore, A. Zykov 사이에서 그래프 작업을 했습니다.

역사적으로 그래프 이론은 200여 년 전 퍼즐을 푸는 과정에서 탄생했습니다. 매우 오랫동안 그녀는 과학자들의 주요 연구 방향에서 떨어져 있었고 그녀는 일반적인 관심의 중심에있을 때만 재능이 완전히 드러난 신데렐라의 입장에서 수학 영역에있었습니다.

유명한 스위스 수학자 오일러(L. Euler)의 그래프 이론에 대한 첫 번째 작업은 1736년에 나타났습니다. 그래프 이론의 발전에 대한 자극은 19세기와 20세기 전환기에 있었습니다. 가장 밀접한 관계를 갖는 토폴로지와 조합이 극적으로 증가했습니다. 그래프는 전기 회로도 및 분자 회로의 구성에 사용되기 시작했습니다. 별도의 수학 분야로서 그래프 이론은 20세기 30년대 헝가리 수학자 Koenig의 연구에서 처음 소개되었습니다.

최근에는 그래프와 관련 연구 방법이 다양한 수준에서 거의 모든 현대 수학에 유기적으로 스며들어 있습니다. 그래프 이론은 토폴로지의 한 분야로 간주됩니다. 또한 대수학 및 정수론과 직접 관련이 있습니다. 그래프는 계획 및 관리 이론, 스케줄링 이론, 사회학, 수학 언어학, 경제학, 생물학, 의학 및 지리학에서 효과적으로 사용됩니다. 그래프는 프로그래밍, 유한 오토마타 이론, 전자공학, 확률 및 조합 문제 해결, 최단 거리 등과 같은 영역에서 널리 사용됩니다. 수학 엔터테인먼트 및 퍼즐도 그래프 이론의 일부입니다. 그래프 이론은 빠르게 발전하여 새로운 응용 분야를 찾고 있습니다.

섹션 2. 그래프의 주요 유형, 개념 및 구조.

그래프 이론은 수학자들의 노력으로 만들어진 수학적 학문이므로 그 표현에는 필요한 엄격한 정의가 포함됩니다.

그래프는 그래프의 꼭짓점이라고 하는 유한한 수의 점과 그래프의 모서리 또는 호라고 하는 이러한 선의 꼭짓점 중 일부를 쌍으로 연결하는 집합입니다.

번호 그래프 이름 정의 그림 이러한 유형의 그래프 사용 예

1 영 그래프 속하지 않는 그래프의 정점 문제: Arkady, Boris. 회의에서 블라디미르, 그리고리, 드미트리는 아무도 없이 악수를 했고, 각자 한 번씩 악수를 했다. 총 에지가 몇 개인지를 격리라고 합니다. 악수했다? 핸드셰이크가 아직 발생하지 않은 순간에 해당하는 상황은 그림과 같은 점선도이다.

고립된 꼭짓점으로만 구성된 그래프를 널 그래프라고 합니다.

표기법: O" - 꼭짓점이 있고 모서리가 없는 그래프

2 완전한 그래프 각 꼭짓점 쌍이 있는 그래프 완전한 그래프에 n개의 꼭짓점이 있는 경우 가장자리 수는 다음과 같습니다. All handshakes are made.

표기법: U"는 n 10으로 구성된 그래프입니다.

이 꼭짓점의 가능한 모든 쌍을 연결하는 꼭짓점과 가장자리. 이러한 그래프는 모든 대각선이 그려진 n-gon으로 나타낼 수 있습니다.

3 불완전한 그래프 아직 모든 악수가 완료되지 않은 상황에서 악수 A와 B, A와 D, E와 가능한 간선을 불완전 D, C, E라고 하는 그래프.

4 그래프의 경로. 주기. 한 꼭짓점에서 다른 꼭짓점으로 가는 그래프의 경로 A 지점에는 제설차용 차고가 있습니다. 차량 운전자는 사진 속 시내 일부 도로에서 눈을 치우라는 지시를 받은 것으로 전해졌다. 차고가있는 교차로에서 작업을 완료 할 수 있습니까? 도시의이 거리 사이에 각 도로를 따라 한 번만 경로를 놓을 수 있다면?

봉우리.

이 경우 경로의 가장자리가 두 번 이상 발생하지 않아야 합니다. 그래프의 모든 모서리를 통과하고 경로가 놓여 있는 닫힌 경로는 그래프의 모든 정점의 차수가 짝수인 경우 각 모서리에 대해 한 번만 호출되기 때문에 정점에서 불가능합니다.

길의 시작, 길 끝의 정상 -

길의 끝. 사이클은 경로이며, 그림에서 그래프를 사용하여 시작과 끝이 일치하는 인구 밀집 지역 간의 도로 다이어그램이 표시됩니다. 간단한 포인트.

사이클은 통과하지 않는 사이클입니다. 예를 들어 A 지점(그래프 상단)에서 H 지점까지는 ADGH, AEH, AEFCEH, ABCEH와 같은 다양한 경로를 통해 도달할 수 있습니다.

그래프의 정점 중 하나를 통해 둘 이상 AEH 경로와 AEFCEH 경로의 차이점은 무엇입니까?

타임스. 지점 E의 "교차로"에 있는 두 번째 경로에서 우리는 두 번 방문했습니다.

이 경로는 AEH보다 깁니다. 경로 AEH는 경로에서 얻을 수 있습니다.

사이클에 모든 에지가 포함된 경우 AEFCEH는 마지막 경로에서 FCE 경로를 "삭제"합니다.

그래프를 한 번, 그런 다음 경로 AEH는 그래프의 경로이지만 경로 AEFCEH는 경로가 아닙니다.

오일러선이라고 한다.

연결된 그래프와 연결이 끊긴 그래프. 정의 1: 12dm 길이의 와이어에서 길이 가장자리가 있는 큐브 프레임을 만들 수 있습니까?

그래프의 두 꼭짓점을 연결(1dm)이라고 하며 와이어가 끊어지지 않습니까?

그래프에 이 정점에서 끝나는 경로가 있는 경우. 이러한 경로가 없으면 정점을 연결되지 않음이라고 합니다.

그래프의 모든 모서리를 통과하고 각 모서리를 따라 한 번만 통과하는 경로는 다음과 같은 경우에만 존재합니다.

1) 각 꼭짓점의 차수가 짝수일 때(경로가 닫힌 경우)

2) 차수가 홀수인 꼭짓점이 두 개뿐인 경우.

정의 2:

그래프의 정점 쌍이 모두 연결되어 있으면 연결됨이라고 합니다.

그래프에 연결이 끊긴 정점 쌍이 하나 이상 있으면 연결이 끊긴 그래프라고 합니다.

6 트리 트리는 연결된 그래프(부록 1)입니다. Zholmurzaeva Tomiris의 가계도.

상의. 나무로만 구성된 연결이 끊긴 그래프를 포리스트라고 합니다.

7 동형 그래프. 그림에 표시된 그래프는 동일한 정보를 제공합니다. 이러한 그래프를 동형(동일)이라고 합니다.

8 평면 그래프의 개념 Task에 표현할 수 있는 그래프. 3개의 다른 집에서 3개의 비행기가 서로 말다툼을 하는 이웃에 살고 있습니다. 그들의 집에서 갈비뼈가 교차하는 곳에서 멀지 않은 곳에 세 개의 우물이 있습니다. 꼭대기에서만 가능한가, 각 우물에 평평하게 누워 각 집이라고합니다. 둘 중 하나가 교차하지 않도록 경로?

솔루션: 8개의 경로를 그린 후 이전에 그린 경로와 교차하지 않는 9번째 경로를 그리는 것이 불가능하다는 것을 확인할 수 있습니다.

정점이 있는 그래프를 구성합니다.

A, B, C, 1, 2, 3

문제의 조건은 집과 우물에 해당하며 다른 가장자리와 교차하지 않는 그래프의 가장자리인 9번째 경로를 그릴 수 없음을 증명하려고 합니다.

그림의 그래프에 그려진 모서리

A1, A2, A3 및 B1, B2, VZ(집 A와 B에서 모든 우물까지의 경로에 해당).

구성된 그래프는 평면을 X, Y, Z의 세 영역으로 나눴습니다. 평면에서의 위치에 따라 정점 B는 이 세 영역 중 하나에 속합니다. 3개의 정점 히트 각각을 고려한다면

B를 X, Y 또는 Z 영역 중 하나로 이동한 다음 그래프의 정점 중 하나가 1, 2 또는 3인지 매번 확인합니다.

(우물 중 하나)는 정점 B에 "접근할 수 없습니다"(즉, 그래프에서 이미 가장자리와 교차하지 않는 가장자리 B1, B2 또는 B3 중 하나를 그리는 것이 불가능함).

작업 질문에 대한 대답은 "불가능합니다!"입니다.

방향 그래프 그래프의 정점 중 하나가 이 가장자리의 시작으로 간주되고 다른 정점이 끝으로 간주되는 경우 그래프의 가장자리를 방향 가장자리라고 합니다.

모든 간선이 방향이 있는 그래프를 방향 그래프라고 합니다.

그래서 그래프 이론의 기본 개념을 고려하여 정리를 증명하고 결과적으로 문제를 해결하는 것이 불가능합니다.

완료된 작업에 대한 결론:

모든 정보 자료를 테이블로 구성하는 방법을 배웠습니다.

이론적 자료의 구성은 그래프 유형 및 응용 프로그램의 시각적 표현에 기여합니다.

그녀는 가계도를 작성할 때 그래프 이론을 적용한 예를 찾았습니다.

신청서 번호 1.

족보

Zholmurzaeva Tomiris의 가계도를 만드십시오.

솔루션 방법.

문제를 해결하는 그래픽 방식.

문제를 해결하는 그래픽 방식은 "논리적 조건의 트리"를 그리는 것입니다. "Tree"는 친척 간의 논리적 관계를 간단한 그림의 형태로 표현합니다. 트리의 각 세대는 하나의 분기에 해당합니다.

예를 들어, 저는 제 가계도를 가져왔습니다.

섹션 3. 그래프 이론의 적용.

우리는 가능한 것보다 더 자주 그래프를 만납니다. 언뜻보기에는 보입니다. 그래프의 예는 로드맵, 전기 회로, 다각형 그리기 등이 될 수 있습니다. 오랫동안 그래프 이론은 주로 논리적 문제를 해결하는 데 사용되었다고 믿어졌습니다. 논리적인 문제를 풀 때 문제에 주어진 수많은 조건들을 기억하고 그것들을 연결짓는 것이 어려운 경우가 많은데, 그래프는 이러한 문제를 푸는 데 도움을 주어 문제의 데이터 간의 관계를 시각화할 수 있게 해줍니다. 그래프 이론 자체는 기하학의 일부로 간주되었습니다. 그러나 20세기에는 그래프 이론의 광범위한 응용이 경제학, 생물학, 화학, 전자공학, 네트워크 계획, 조합론 및 기타 과학 및 기술 분야. 그 결과 급속도로 발전하기 시작하여 독립적인 분지론으로 바뀌었고, 그래프를 사용할 수 있다면 많은 수학적 문제의 해결이 단순화됩니다. 그래프 형태의 데이터 표시는 가시성을 제공합니다. 그래프를 사용하면 많은 증명도 단순화되고 더 설득력이 생깁니다.

3. 1. 기하 문제와 정리에 그래프를 적용합니다.

그래프의 도움으로 증명 가능한 진술로 이어지는 논리적 결과의 사슬을 쉽게 설정할 수 있습니다. 정리의 증명과 문제의 해를 간단하고 정확하게 서술하시오.

이등변 삼각형의 밑변에 있는 꼭짓점에서 그린 이등분선이 같다는 것을 증명하십시오.

솔루션 방법.

추론으로 문제를 증명합니다.

ABC를 다음과 같은 이등변 삼각형이라고 하자.

B1 A1 밑변 AB 및 이등분선 AA1 및 BB1.

∆ABB1 및 ∆BAA1을 고려하십시오. ∟B1AB=

∟A1BA는 이등변 삼각형 ∆ABC의 밑변에서의 각입니다. ∟ABB1= ∟A1AB

AA1과 BB1은 이등변 삼각형의 밑변에서 각의 이등분선이므로 A B. AB는 공통 측면입니다. 수단

∆ABB1 = ∆BAB1 측면과 인접한 두 모서리를 따라. 삼각형의 평등에서 측면 AA1과 BB1의 평등이 따릅니다.

그래프를 사용하여 문제를 증명합니다.

증명: AA=BB

추론을 위해 그래프를 사용합시다. 그래프의 꼭짓점은 정리 또는 문제의 조건과 증명의 단계입니다.

그래프의 모서리는 논리적 결과입니다. 그래프 구성표의 끝은 증명할 주장입니다.

색상은 구성 요소를 강조 표시하는 데 사용됩니다. 정리의 조건과 문제는 파란색입니다. 증명할 주장은 빨간색입니다. 증거 단계는 검은색입니다.

정리를 증명하고 문제를 해결하는 설명 된 형식은 정리를 증명하고 문제를 해결하는 주요 단계를 골라 낼 수 있기 때문에 학생들에게 유용하고 편리합니다.

3. 2. 프로그램-방법적 복합체.

a) 교사용 가이드.

제안 된 매뉴얼은 A. V. Pogorelov의 7-9 학년 기하학 교과서에 따라 편집되었습니다. 그 주요 목적은 기하학을 가르치는 교사를 돕기 위해 필요한 시각 보조 장치와 함께 기하학을 연구하는 과정을 제공하는 것입니다. 정리를 증명하는 과정을 촉진하고 문제를 해결하는 과정에서 이론적 자료의 동화를 촉진합니다. 그래프 다이어그램은 본질적으로 다차원적이며 클래스의 목표와 형태에 따라 다양한 방식으로 사용될 수 있습니다. 개별 및 정면 조사를 수행하는 데 사용되는 카드로 사용됩니다(작업이 있는 그래프 다이어그램). 이 매뉴얼에는 학생 워크북이 포함되어 있습니다. 워크북을 사용하여 정리할 수 있습니다. 독립적 인 일학교 시간 중 및 방과 후 학생.

b) 학생용 워크북.

매뉴얼은 워크북 형식으로 되어 있습니다. 매뉴얼에는 정리가 있는 28개의 그래프 구성표와 작업이 있는 28개의 그래프 구성표가 포함되어 있습니다. 그래프 다이어그램에는 필요한 명확성과 솔루션의 프레임워크를 나타내는 주요 프로그램 자료가 포함되어 있습니다. 학생들은 문제에 대한 해결책을 구성하는 정보로 빈 칸을 순차적으로 채웁니다.

색상은 구성 요소를 강조 표시하는 데 사용됩니다. 정리의 조건과 문제는 파란색, 증명되는 주장은 빨간색, 증명의 단계는 검은색입니다.

이 매뉴얼은 7-9학년 학생들에게 유용합니다.

c) 전자 매뉴얼.

작업 결과 및 토론. 이 프로젝트는 학교 수학 과정에서 그래프 사용에 대한 2년 연구의 결과입니다.

프로그래밍 방식으로 생성 - 체계적인 콤플렉스구현은 다음과 같은 과정에서 수행되었습니다.

"그래프를 사용하여 논리적 문제 해결"이라는 주제로 "아리스토텔레스"클럽의 수업을 진행합니다.

기하학적 정리 및 문제 증명에 그래프 적용

8.9학년 기하학 수업에서.

학교 과학 및 실습 회의에서 프로젝트 프레젠테이션.

결론.

학교 기하학 과정에서 그래프 사용에 대한 연구 결과를 요약하면 다음과 같은 결론에 도달했습니다.

1. 기존의 것보다 정리 및 문제 해결의 그래프 증명의 장점은 정리 및 문제 증명의 역학을 설명한다는 것입니다.

2. 기하정리의 증명과정과 그래프기법의 문제를 소개함으로써 학생들의 증명구성 능력을 강화할 수 있다.

3. 7-9 학년에서 기하학을 공부하기 위해 개발된 소프트웨어 및 방법론적 복합체: a) 교사를 위한 안내서; b) 학생용 워크북 c) 전자 매뉴얼은 7-9학년 학생들에게 유용합니다.

교육용 에디션

유유킨 니콜라이 알렉세비치

LR 번호 인쇄용으로 서명됨

어. 에드. 나.., .

보로네시 주립 기술 대학

394026 Voronezh, Moskovsky Ave. 십사

자기 디스크 디렉토리

고등 수학 및 물리 및 수리 모델링학과

에. 유유킨

이산 수학 1부. 그래프 이론의 요소

지도 시간

에. 유유킨

이산 수학 1부. 그래프 이론의 요소

지도 시간

보로네시 2004

소개

이 매뉴얼은 다음 전문 분야에서 공부하는 VSTU 학생들이 "이산 수학" 과정에서 사용할 수 있습니다.

090102 - 컴퓨터 보안;

090105 - 자동화 시스템의 포괄적인 정보 보안;

090106 - 통신 시스템의 정보 보안.

"Discrete Mathematics"분야는 주, 일반 교육 표준에 따라 지식과 기술의 습득을 제공하는 동시에 다음을 얻는 데 기여합니다. 기초 교육, 세계관의 형성과 논리적 사고의 발달.

그래프 이론은 이산 객체와 관련된 현대 공학 문제를 공식화하는 효과적인 도구입니다. 집적 회로 및 제어 회로 설계, 자동 장치 및 논리 회로 연구, 시스템 분석, 자동화 생산 제어, 컴퓨터 및 정보 네트워크 개발, 회로 및 설계 토폴로지 설계 등에 사용됩니다.

에 학습 가이드그래프 이론의 기초, 기본 방법 및 알고리즘을 설명합니다. 다음은 n-그래프와 쌍곡선입니다. 동형사상; 나무; 오일러 그래프; 평면 그래프; 덮개 및 독립 세트; 강력한 연결

안에 쌍곡선; 마르코프 체인 그래프 분석; 그래프에서 최단 경로를 찾는 알고리즘; 해밀턴 주기를 찾는 문제

안에 그래프; 여행하는 세일즈맨 문제; 그래프 및 매핑의 열거; 극한 작업; 최적화 작업; 보편적인 작업; 분기 및 바인딩 방법; 뿐만 아니라 위의 개념을 사용하여 실용적인 기술을 개발합니다.

이 과정의 목적은 자연 과학 및 공학의 모델링 과정 및 현상 분야에서 학생들의 이론적 지식, 실용적인 기술 및 능력을 개발하는 것입니다.

ke, 높은 전문 수준에서 정보 보안 분야의 공식 활동을 수행하는 데 필요한 개체의 양적 및 질적 관계를 표현하기 위해 수학 기호를 사용할 가능성이 있습니다.

이 목표를 달성하기 위해 다음 작업을 수행합니다.

그래프 이론의 가능한 가장 넓은 범위의 개념을 연구합니다.

교육 및 실제 문제를 해결하는 기술을 습득합니다.

최적화의 마스터 방법;

정보 문제를 설정하고 해결하고 그래프를 사용하여 정보를 모델링 및 분석하는 기술을 개발합니다.

학문 "이산 수학"은 응용 수학 분야 중 하나입니다. "대수학" 및 "수학적 논리 및 알고리즘 이론" 분야의 연구에서 학생들이 습득한 지식을 기반으로 합니다. "이산 수학" 분야의 연구에서 얻은 지식과 기술이 연구에 사용됩니다. 일반 전문가및 특수 분야.

1. 그래프 이론의 기본 개념.

1.1. 그래프 이론의 문제.

그래프 이론은 관계의 개념으로 수행되는 것처럼 서로 다른 대상 간의 관계 시스템을 연구하는 수학의 한 분야입니다. 그러나 그래프의 독립적인 정의는 이론의 표현을 단순화하고 더 이해하기 쉽고 시각적으로 만듭니다.

그래프 이론의 첫 번째 문제는 레크리에이션 문제와 퍼즐을 푸는 것과 관련이 있습니다.

첫 번째 작업입니다. 쾨니히스베르크 다리의 문제는 1786년 오일러에 의해 제기되고 해결되었습니다. 이 도시는 Pregolya 강의 은행과 두 개의 섬에 위치하고 있습니다. 섬은 그림과 같이 7개의 다리로 해안과 섬을 연결했습니다.

질문이 생겼습니다. 집을 나간 후 각 다리를 정확히 한 번 건너 다시 돌아올 수 있습니까?

두 번째 과제. 세 집과 세 우물의 문제. 세 집과 세 우물이 있습니다.

경로가 교차하지 않도록 각 집에서 각 우물까지 경로를 그려야 합니다. 과제는

Pontryagin에 의해 해결되고 Kuratovsky에 의해 독립적으로 해결됨

세 번째 과제. 대략 4가지 색상입니다. 인접한 두 영역이 같은 색으로 칠해지지 않도록 평면의 모든 지도를 네 가지 색으로 칠합니다.

그래프 이론의 많은 결과는 과학 기술의 실제 문제를 해결하는 데 사용됩니다. 그래서 19세기 중반에 Kirchhoff는 복잡한 전기 회로를 계산하기 위해 그래프 이론을 적용했습니다. 그러나 수학적 학문으로서 그래프 이론은 20세기의 30년대에만 형성되었다. 이 경우 그래프는 추상적인 수학적 개체로 간주됩니다. 그들은 회로 및 시스템의 분석 및 합성, 네트워크 계획 및 관리, 운영 연구, 프로그래밍, 유기체의 생명 모델링 및 기타 영역에서 사용됩니다.

1.2. 기본 정의.

그래프 G= (V,E )는 비어 있지 않은 정점 V 세트와 정렬되지 않고 정렬된 정점 E 쌍의 두 세트 모음입니다. 다음에서는 유한 그래프가 고려됩니다. 유한한 정점 집합과 유한한 쌍의 집합이 있는 그래프. 정렬되지 않은 정점 쌍을 모서리라고 하고 정렬된 쌍을 호라고 합니다.

일반적으로 그래프는 정점 - 점(또는 원), 모서리 - 임의 구성의 선과 같은 다이어그램으로 표시됩니다. 호에서 추가 화살표는 방향을 나타냅니다. 그래프가 표시될 때

리브의 기하학적 특성(길이, 곡률) 및 상호 합의평면의 정점.

모서리(호)에 속하지 않는 정점을 격리라고 합니다. 모서리 또는 호로 연결된 정점을 인접 정점이라고 합니다. 모서리(호)와 두 정점 중 하나를 입사라고 합니다.

모서리(u,v)는 꼭짓점 u와 v를 연결하고 호(u,v)는 꼭짓점 u에서 시작하여 꼭짓점 v에서 끝나는 반면 u를 시작이라고 하고 v를 끝이라고 합니다. 이 호의.

한 쌍의 정점은 둘 이상의 가장자리(같은 방향의 호)로 연결할 수 있습니다. 이러한 모서리(호)를 배수라고 합니다. 호(또는 모서리)는 동일한 정점에서 시작하거나 끝날 수 있습니다. 이러한 호(가장자리)를 루프라고 합니다. 루프를 포함하는 그래프를 의사 그래프라고 합니다. 다중 간선(호)이 있는 그래프를 다중 그래프라고 합니다.

루프와 다중 간선이 없는 그래프를 단순 그래프라고 합니다. 정점의 쌍에 대해 연결하는 모서리(호)가 있는 경우 간단한 그래프를 완료라고 합니다. n개의 꼭짓점이 있는 완전한 그래프는 K n 으로 표시됩니다. 예를 들어 다음은 그래프입니다.

하나의 고립된 꼭짓점(K 1 )으로 구성된 그래프를 trivial이라고 합니다.

그래프 G의 보수는 그래프 G와 같은 꼭짓점을 갖고 완전한 그래프를 얻기 위해 그래프 G에 추가해야 하는 간선을 포함하는 그래프 G입니다.

모든 non-digraph에 정식으로 해당동일한 꼭짓점 집합을 갖는 방향 그래프로, 각 모서리는 동일한 꼭짓점에 입사하고 반대 방향을 갖는 두 개의 호로 대체됩니다.

1.3. 정점 각도를 그래프로 표시합니다.

단순 그래프 G의 꼭짓점 v의 차수(원자)(표기 d(v) 또는 deg(v))는 주어진 꼭짓점 v에 입사하는 모서리 또는 호의 수입니다. 의사 그래프 정점의 원자가를 계산할 때 각 루프는 두 번 계산되어야 합니다.

n 그래프의 모든 꼭짓점의 차수가 k와 같으면 그래프를 호출합니다. 규칙적인(균질한)학위 k. 정점의 차수가 0이면 격리됩니다. 꼭짓점의 차수가 1이면 꼭짓점을 터미널(매달린, 막다른 골목)이라고 합니다.

digraph의 경우 정점 v에서 나가는 호의 수를

vaetsya 절반 정도의 결과				(v ) 및 들어오는 - 세미 -

새로운 일몰 d			(v ), 관계식 d(v )=

	(동)+	(V).

오일러의 정리: 그래프의 꼭짓점 차수의 합은 다음과 같습니다.

모서리 수의 두 배, 즉

d(vi)



			(V)

여기서 n은 정점의 수입니다. m - 숫자

갈비뼈(호). 이 진술은 정점 각도의 합을 계산할 때 각 모서리가 모서리의 한쪽 끝과 다른 쪽 끝에서 두 번 고려된다는 사실에 의해 입증됩니다.

1.4. 그래프 동형.

그래프의 정점이 어떤 면에서 서로 다른 경우 그래프를 레이블이 지정된(또는 번호가 다시 매겨진) 그래프라고 합니다.

표시(숫자). 고려된 수 엄격한 의미에서 완전히 정의, 정점과 모서리의 번호가 고정되어 있는 경우. 이 경우 그래프 G 1 과 G 2 는 꼭짓점과 모서리 집합이 일치하는 경우 같음(표시 G 1 = G 2 ) , 이라고 합니다. 두 개의 그래프 또는 의사 그래프 G 1 = (V 1 ,E 1 ) 및 G 2 = (V 2 ,E 2 )라고 합니다.

	동형(표기 G	만일 거기에

	일대일 매핑: 1)	: V 1 V 2
: E 1 E 2 그래프에서 임의의 두 정점 u, v에 대해
	((u , v )) ((u ), (v )) 관계가 유효합니다.

	두 개의 간단한 그래프(루프 및 다중 간선 없음) G 1		및 G2

서로 동일한 경우 동형으로 판명

가치 매핑

: V 1 V 2

그런

(u , v ) ((u ), (v )) .

따라서 그래프는 꼭짓점과 모서리의 번호만 다를 경우 동형입니다. 그래프 동형은 다음과 같은 속성을 갖기 때문에 등가 관계입니다.

반사성 -

G1,

게다가, 전향

동일한 기능입니다.

대칭.

전단법으로

전이성.

지 1 지 2

전단사

1,아

전단법으로

그럼 GG

전단법으로

2 (1 ) .

그래프 이론은 예를 들어 지리 정보 시스템(GIS)에서 응용 프로그램을 찾습니다. 기존 또는 새로 설계된 주택, 구조물, 숙소 등을 정점으로 간주하고 이를 연결하는 도로, 엔지니어링 네트워크, 전력선 등을 가장자리로 간주합니다. 이러한 그래프에 대한 다양한 계산을 사용하면 예를 들어 가장 짧은 우회로나 가장 가까운 식료품점을 찾아 최적의 경로를 계획할 수 있습니다.

그래프 이론에는 수많은 미해결 문제와 입증되지 않은 가설이 포함됩니다.

그래프 이론의 주요 응용 분야:

화학에서(구조, 복잡한 반응 방식을 설명하기 위해 위상 규칙은 그래프 이론의 문제로 해석될 수도 있음); 컴퓨터 화학은 그래프 이론을 응용한 비교적 젊은 화학 분야입니다. 그래프 이론은 화학정보학의 수학적 기초입니다. 그래프 이론을 사용하면 이론적으로 가능한 탄화수소 및 기타 유기 화합물의 이성질체 수를 정확하게 결정할 수 있습니다.

컴퓨터 과학 및 프로그래밍(알고리즘 그래프 다이어그램);

통신 및 운송 시스템에서. 특히 인터넷에서 데이터를 라우팅하는 경우;

경제학에서;

물류;

회로 공학에서(인쇄 회로 기판 또는 미세 회로의 요소 상호 연결 토폴로지는 그래프 또는 하이퍼그래프임).

특별한 종류의 그래프가 있습니다. 목재.목재연결된 비순환 그래프입니다. 연결성은 정점 쌍 사이에 경로가 있음을 의미하고, 비순환성은 순환이 없고 정점 쌍 사이에 경로가 하나만 있다는 사실을 의미합니다. 에 그림 1.3제출된 이진 트리.

이진 트리각 노드가 최대 2개의 데이터를 갖는 트리형 데이터 구조 자손(어린이들). 일반적으로 첫 번째 것을 호출합니다. 부모 노드그리고 아이들의 이름은 좌익그리고 권리 상속인.

그래프의 행렬 표현. 사건 매트릭스.

그래프 속성 분석에 대한 알고리즘 접근 방식의 개발은 컴퓨터를 사용하는 것을 포함하여 실제 계산에 더 적합한 그래프를 설명하는 특정 방법을 필요로 합니다. 그래프를 나타내는 세 가지 가장 일반적인 방법을 고려하십시오.

무방향 그래프의 모든 꼭짓점과 모든 모서리 또는 유향 그래프의 모든 꼭짓점과 모든 호(루프 포함)가 1부터 시작하여 번호가 매겨진다고 가정합니다. 그래프(무향 또는 유향)는 유형의 행렬로 나타낼 수 있습니다. 여기서 는 꼭짓점의 수이고 는 모서리(또는 호)의 수입니다. 무방향 그래프의 경우 이 행렬의 요소는 다음과 같이 지정됩니다.

방향 그래프의 경우 행렬 요소는 다음과 같이 지정됩니다.

이렇게 정의된 유형 행렬을 사건 매트릭스.

입사 행렬을 구하는 예. 아래에 표시된 그래프의 경우( 쌀. 2.1 ㄱ그림 2.1 b).

그림 2.1 a 그림. 2.1나

인접 행렬.

입사 행렬 형태의 그래프 표현이 이론적 연구에서 매우 중요한 역할을 한다는 사실에도 불구하고 실제로 이 방법은 매우 비효율적입니다. 우선, 각 열의 행렬에는 0이 아닌 요소가 두 개뿐이므로 많은 수의 꼭짓점으로 그래프를 표현하는 이 방법은 비경제적입니다. 또한 입사 행렬을 사용하여 실제 문제를 해결하는 것은 매우 어렵습니다.

예를 들어, 입사 행렬을 사용하여 유향 그래프에서 이러한 간단한 문제를 해결하는 데 소요된 시간을 추정해 보겠습니다. 주어진 정점에 대해 해당 정점의 "환경"을 찾으십시오. 직접 도달할 수 있는 모든 정점의 집합과 직접 도달할 수 있는 모든 정점의 집합입니다.

이 문제를 해결하려면 유향 그래프의 입사 행렬에서 0이 아닌 요소(+1 또는 -1)가 나타날 때까지 숫자가 있는 행을 따라 가야 합니다. +1이 발견되면 해당 열에서 숫자 -1이 기록된 행을 찾아야 합니다. 이 번호를 포함하는 라인의 번호는 주어진 꼭짓점에서 직접 도달할 수 있는 꼭짓점의 번호를 나타냅니다. -1이 발견되면 열에서 1이 쓰여진 줄을 찾고 이 꼭짓점에 직접 도달할 수 있는 꼭짓점의 번호를 가져와야 합니다. 전체 "환경"을 얻으려면 0이 아닌 모든 요소에 대해 지정된 검색을 수행해야 합니다. k번째 라인. 가장 시간이 많이 걸리는 절차는 열에서 null이 아닌 요소를 찾는 것입니다. 이러한 탐색 절차의 수는 정점의 차수와 같습니다. 이 경우 정점의 환경을 분석하기 위한 알고리즘의 복잡성은 (~ 정도)라고 말할 것입니다.

모든 꼭짓점의 "환경"을 찾는 데는 방향 그래프의 꼭짓점 수에 모든 꼭짓점의 차수의 합을 곱한 값의 곱의 순서로 시간이 소요됨을 알 수 있습니다. 방향 그래프의 호 수. 따라서 "환경" 검색 알고리즘의 복잡성은 다음과 같습니다. 검색은 정점의 수와 호의 수의 곱의 순서로 시간이 걸립니다.

그래프를 나타내는 보다 효율적인 행렬 구조는 다음과 같습니다. 꼭짓점 인접 행렬, 또는 부울 행렬그래프. 이것은 차수의 정방 행렬 B입니다. N, 요소는 다음과 같이 정의됩니다.

무방향 그래프의 경우:

유향 그래프의 경우:

아래에 표시된 그래프의 경우( 쌀. 2.2 에이) 입사 행렬은 ( 그림 2.2 b).

작품의 텍스트는 이미지와 수식 없이 배치됩니다.
풀 버전작업은 PDF 형식의 "작업 파일" 탭에서 사용할 수 있습니다.

소개

"수학에서 기억해야 할 것은 공식이 아니라 사고하는 과정이다..."

E. I. 이그나티예프

그래프 이론은 현재 집중적으로 발전하고 있는 수학의 한 분야입니다. 이것은 많은 사물과 상황이 사회생활의 정상적인 기능에 매우 중요한 그래프 모델의 형태로 기술된다는 사실로 설명된다. 더 자세한 연구의 관련성을 결정하는 것은 바로 이 요소입니다. 따라서 이 작업의 주제는 매우 적절합니다.

표적 연구 작업: 다양한 지식 분야에서 그래프 이론을 응용하고 논리적인 문제를 풀 때의 특징을 알아본다.

목표는 다음을 식별했습니다. 작업:

그래프 이론의 역사에 대해 배우십시오.

그래프 이론의 기본 개념과 그래프의 주요 특성을 학습합니다.

다양한 지식 분야에서 그래프 이론의 실제 적용을 보여줍니다.

그래프를 사용하여 문제를 해결하는 방법을 고려하고 자신의 문제를 만듭니다.

객체연구: 그래프 방법의 적용을 위한 인간 활동의 범위.

주제연구: 수학 "그래프 이론" 섹션.

가설.그래프 이론의 연구는 학생들이 미래의 관심을 결정할 수학의 논리적 문제를 해결하는 데 도움이 될 수 있다고 가정합니다.

행동 양식연구 작업:

연구 과정에서 다음과 같은 방법이 사용되었습니다.

1) 다양한 정보 소스와 협력합니다.

2) 자료의 설명, 수집, 체계화.

3) 관찰, 분석 및 비교.

4) 작업을 작성합니다.

이론적 및 실제적 중요성이 작업의 결과가 컴퓨터 과학, 수학, 기하학, 그림 및 수업 시간뿐만 아니라 이 주제에 관심이 있는 광범위한 독자에게 사용될 수 있다는 사실에 의해 결정됩니다. 저자는 많은 지식 분야에서 그래프 사용에 대한 수많은 예를 제시하고 자신의 작업을 공식화했기 때문에 연구 작업은 뚜렷한 실용적인 방향을 가지고 있습니다. 이 자료는 수학의 선택 과목에서 사용할 수 있습니다.

제1장 연구주제에 대한 이론적 검토

수학에서 "그래프"는 선으로 연결된 여러 점인 그림으로 나타낼 수 있습니다. "백작"은 라틴어 "graphio"에서 유래했습니다. 귀족의 잘 알려진 제목처럼 씁니다.

수학에서 그래프의 정의는 다음과 같습니다.

수학에서 "그래프"라는 용어는 다음과 같이 정의됩니다.

그래프 유한 점 집합입니다. 봉우리, 선으로 연결할 수 있는 것 - 갈비 살 .

그래프의 예에는 다각형, 전기 회로, 항공사, 지하철, 도로 등의 개략도가 포함됩니다. 계보 트리는 속 구성원이 꼭짓점 역할을 하고 가족 관계가 그래프 가장자리 역할을 하는 그래프이기도 합니다.

쌀. 하나그래프 예

한 꼭짓점에 속하는 모서리의 수를 이라고 합니다. 그래프 꼭짓점 차수 . 꼭짓점의 차수가 홀수이면 꼭짓점을 - 이상한 . 꼭짓점의 차수가 짝수이면 꼭짓점이라고합니다. 조차.

쌀. 2그래프 상단

널 그래프 간선으로 연결되지 않은 격리된 꼭짓점으로만 구성된 그래프입니다.

완전한 그래프 는 각 정점 쌍이 간선으로 연결된 그래프입니다. 모든 대각선을 포함하는 N-gon은 완전한 그래프의 예입니다.

그래프에서 시작점과 끝점이 동일한 경로를 선택하면 이러한 경로를 그래프 주기 . 그래프의 각 꼭짓점을 통과하는 경로가 최대 한 번만 발생하면 주기~라고 불리는 단순한 .

그래프의 모든 두 정점이 간선으로 연결되어 있으면 연결된 그래프. 카운트가 호출됩니다 관련 없는 연결되지 않은 정점이 한 쌍 이상 있는 경우.

그래프가 연결되어 있지만 사이클을 포함하지 않는 경우 이러한 그래프를 나무 .

백작의 길 하나의 공통 꼭짓점을 가진 두 개의 인접한 모서리가 모두 한 번만 발생하는 시퀀스입니다.

가장 짧은 정점 체인의 길이 ㅏ그리고 b는 호출된다 거리 봉우리 사이 ㅏ그리고 b.

꼭지점 ㅏ~라고 불리는 센터 정점 사이의 거리가 있는 경우 그래프 ㅏ다른 정점은 가능한 가장 작은 정점입니다. 그러한 거리는 반지름 그래프.

그래프의 두 꼭짓점 사이의 가능한 최대 거리를 지름 그래프.

그래프 채색 및 적용.

지리 지도를 자세히 보면 그래프인 철도나 고속도로를 볼 수 있습니다. 또한 국가(지구, 지역) 간의 경계로 구성된 카트라에 그래프가 있습니다.

1852년 영국 학생 Francis Guthrie는 영국 지도를 색칠하고 각 카운티를 별도의 색상으로 강조 표시하는 작업을 받았습니다. 페인트의 선택이 적기 때문에 Guthrie는 페인트를 재사용했습니다. 그는 국경의 공통 부분이있는 카운티가 반드시 다른 색상으로 칠해지도록 색상을 선택했습니다. 다양한 지도를 채색하는 데 필요한 최소 색상 수는 얼마인지에 대한 질문이 제기되었습니다. Francis Guthrie는 증명할 수는 없지만 네 가지 색상이면 충분하다고 제안했습니다. 이 문제는 학생 서클에서 활발하게 논의되었지만 나중에 잊혀졌습니다.

"4색 문제"에 대한 관심이 증가했지만 저명한 수학자들도 해결하지 못했습니다. 1890년 영어 수학자퍼시 히우드(Percy Heawood)는 다섯 가지 색상이 모든 지도를 색칠하기에 충분하다는 것을 증명했습니다. 그리고 1968년에야 그들은 40개 미만의 국가를 표시하는 지도를 색칠하기에 4가지 색상으로 충분하다는 것을 증명할 수 있었습니다.

1976년 이 문제는 두 명의 미국 수학자 Kenneth Appel과 Wolfgant Haken이 컴퓨터를 사용하여 풀었습니다. 이를 해결하기 위해 모든 카드를 2000종류로 나누었습니다. 네 가지 색상으로 충분하지 않은 채색 카드를 식별하기 위해 모든 유형을 검사하는 컴퓨터용 프로그램이 만들어졌습니다. 세 종류의 지도만 컴퓨터로 조사할 수 없었기 때문에 수학자들이 스스로 연구했습니다. 그 결과 4가지 색상이면 2000종의 모든 카드를 채색하기에 충분하다는 것을 알았습니다. 그들은 네 가지 색상의 문제에 대한 해결책을 발표했습니다. 이날 아펠과 하켄이 근무했던 대학의 우체국은 "4색이면 충분하다"는 글과 함께 모든 우표에 우표를 붙였다.

4색의 문제는 약간 다른 방식으로 제시될 수 있습니다.

이렇게 하려면 그래프로 표시하는 임의의 지도를 고려하십시오. 주의 수도는 그래프의 정점이고 그래프의 가장자리는 주에 공통 경계가 있는 정점(자본)을 연결합니다. 이와 같은 그래프를 얻기 위해서는 다음과 같은 문제가 공식화된다. 즉, 4가지 색상을 사용하여 그래프를 채색하여 공통 모서리를 갖는 꼭짓점을 서로 다른 색상으로 채색해야 한다.

오일러 및 해밀턴 그래프

1859년 영국 수학자 William Hamilton은 판매용 퍼즐을 출시했습니다. 각 봉우리에는 세계에서 가장 큰 도시 중 하나인 광저우, 델리, 브뤼셀 등의 이름이 있었습니다. 작업은 각 정점을 한 번만 방문하여 다면체의 가장자리를 따라가는 닫힌 경로를 찾는 것이 었습니다. 경로를 표시하기 위해 카네이션에 고정 된 코드가 사용되었습니다.

해밀턴 순환은 경로가 그래프의 모든 정점을 한 번 통과하는 단순 순환인 그래프입니다.

칼리닌그라드 시(구 Koenigsberg)는 프레겔 강에 위치해 있습니다. 강은 다리로 서로 연결되어 있는 두 개의 섬을 씻어냈습니다. 오래된 다리는 더 이상 존재하지 않습니다. 그들에 대한 기억은 도시의 지도에만 남아 있었다.

어느 날 한 도시의 한 주민이 친구에게 다리를 모두 건너서 다리를 한 번씩만 방문하고 걷기 시작했던 곳으로 돌아갈 수 있냐고 물었다. 이 문제는 많은 마을 사람들의 관심을 끌었지만 아무도 해결할 수 없었습니다. 이 질문은 많은 국가의 과학자들의 관심을 불러일으켰습니다. 이 문제는 수학자 Leonhard Euler에 의해 해결되었습니다. 또한 그는 그러한 문제를 해결하기 위한 일반적인 접근 방식을 공식화했습니다. 이를 위해 그는 지도를 그래프로 만들었습니다. 땅이 이 그래프의 꼭짓점이 되었고, 그것을 연결하는 다리가 가장자리가 되었습니다.

쾨니히스베르크 다리 문제를 풀 때 오일러는 그래프의 속성을 공식화하는 데 성공했습니다.

그래프의 모든 꼭짓점이 짝수인 경우 한 꼭짓점에서 시작하여 같은 꼭짓점에서 한 획으로 끝나는 그래프를 그릴 수 있습니다(같은 선을 따라 두 번 그리지 않고 종이에서 연필을 떼지 않고).

두 개의 홀수 정점이 있는 그래프가 있는 경우 해당 정점도 한 획으로 연결할 수 있습니다. 이렇게 하려면 홀수 정점에서 시작하여 다른 정점에서 끝나야 합니다.

홀수 정점이 2개 이상인 그래프가 있으면 한 획으로 그래프를 그릴 수 없습니다.

이러한 속성을 브리지 문제에 적용하면 연구 중인 그래프의 모든 정점이 홀수임을 알 수 있습니다. 즉, 이 그래프를 한 획으로 연결할 수 없습니다. 모든 다리를 한 번 건너서 여행이 시작된 곳에서 여행을 끝내는 것은 불가능합니다.

그래프에 그래프의 모든 모서리를 한 번 포함하는 사이클(단순한 것은 아님)이 있는 경우 이러한 사이클을 오일러 사이클 . 오일러 체인(경로, 주기, 윤곽)은 그래프의 모든 모서리(호)를 한 번 포함하는 사슬(경로, 주기, 윤곽)입니다.

2장. 연구 및 결과에 대한 설명

2.1. 연구의 단계

가설을 테스트하기 위해 이 연구에는 세 단계가 포함되었습니다(표 1).

연구 단계

1 번 테이블.

		사용된 방법
문제의 이론적 연구	인지 및 과학 문헌을 연구하고 분석합니다.	- 독립적인 사고;  정보 출처 연구; - 필요한 문헌을 검색합니다.
문제에 대한 실제 연구	영역 검토 및 분석 실용적인 응용 프로그램카운트;	- 관찰; - 분석; - 비교; - 질문.
3단계. 결과의 실제 사용	학습된 정보를 요약합니다.	- 체계화;  보고서(구두, 서면, 자료 시연 포함)	2017년 9월

2.2. 그래프의 실용화 분야

그래프 및 정보

정보 이론은 이진 트리의 속성을 광범위하게 사용합니다.

예를 들어, 다양한 길이의 0과 1의 특정 시퀀스 형태로 특정 수의 메시지를 인코딩해야 하는 경우입니다. 평균 단어 길이가 다른 확률 분포와 비교하여 가장 작은 경우 코드 단어의 주어진 확률에 대해 코드가 가장 좋은 것으로 간주됩니다. 이러한 문제를 해결하기 위해 Huffman은 탐색 이론의 틀에서 코드를 그래프 트리로 표현하는 알고리즘을 제안했습니다. 각 꼭짓점에 대해 질문이 제안되며, 이에 대한 대답은 "예" 또는 "아니요"일 수 있습니다. 이는 꼭짓점에서 나오는 두 개의 가장자리에 해당합니다. 이러한 트리의 구성은 필요한 것을 설정한 후 완료됩니다. 이는 이전 질문에 대한 답을 미리 알지 못하고 인터뷰 계획을 이진 트리로 제시하는 다인면접에 적용할 수 있습니다.

그래프 및 화학

A. Cayley조차도 포화 (또는 포화) 탄화수소의 가능한 구조 문제를 고려했으며, 그 분자는 다음 식으로 제공됩니다.

씨앤에이치 2n+2

모든 탄화수소 원자는 4가이고 모든 수소 원자는 1가입니다. 구조식가장 간단한 탄화수소가 표시됩니다.

포화 탄화수소의 각 분자는 트리로 나타낼 수 있습니다. 모든 수소 원자가 제거되면 남아 있는 탄화수소 원자는 4도 이하의 꼭짓점을 가진 트리를 형성합니다. 이것은 가능한 원하는 구조(주어진 물질의 상동체)의 수가 정점 각도가 최대 4인 나무의 수와 같다는 것을 의미합니다. 이 문제는 특정 유형의 나무를 나열하는 문제로 축소됩니다. D. Poya는 이 문제와 그 일반화를 고려했습니다.

그래프 및 생물학

박테리아 번식 과정은 생물학적 이론에서 발견되는 다양한 가지 과정 중 하나입니다. 각 박테리아는 일정 시간이 지나면 죽거나 둘로 나뉩니다. 따라서 한 박테리아에 대해 자손 번식의 이진 트리를 얻습니다. 문제의 문제는 다음과 같습니다. 얼마나 많은 경우가 케이의 자손 n세대하나의 박테리아? 생물학에서 이 비율을 Galton-Watson 과정이라고 하며 필요한 경우의 수를 나타냅니다.

그래프와 물리학

라디오 아마추어에게 어려운 지루한 작업은 인쇄 회로(유전체 판 - 절연 재료 및 금속 스트립 형태의 에칭 트랙)를 만드는 것입니다. 트랙의 교차는 특정 규칙에 따라 특정 지점(3극관, 저항기, 다이오드 등이 설치된 장소)에서만 발생합니다. 결과적으로 과학자는 정점이 있는 평면 그래프를 그리는 작업에 직면해 있습니다.

따라서 위의 모든 사항은 그래프의 실용적인 가치를 확인합니다.

인터넷 수학

인터넷은 정보를 저장하고 전송하기 위해 상호 연결된 컴퓨터 네트워크의 세계적인 시스템입니다.

인터넷은 그래프로 나타낼 수 있는데, 그래프의 꼭짓점은 인터넷 사이트이고 가장자리는 한 사이트에서 다른 사이트로 이동하는 링크(하이퍼링크)입니다.

수십억 개의 꼭짓점과 가장자리를 가진 웹 그래프(인터넷)는 끊임없이 변화하고 있습니다. 사이트는 저절로 추가되고 사라지고, 링크는 사라지고 추가됩니다. 그러나 인터넷은 수학적 구조를 가지고 있으며 그래프 이론을 따르며 몇 가지 "안정된" 속성을 가지고 있습니다.

웹 그래프는 희소합니다. 정점보다 몇 배 더 많은 가장자리를 포함합니다.

희소성에도 불구하고 인터넷은 매우 작습니다. 링크를 사용하여 한 사이트에서 다른 사이트로 5~6번의 클릭으로 이동할 수 있습니다(유명한 "6개의 악수" 이론).

알다시피 그래프의 차수는 꼭짓점이 속하는 간선의 수입니다. 웹 그래프 꼭짓점의 정도는 일정한 법칙에 따라 분포하는데, 링크(가장자리)가 많은 사이트(꼭짓점)의 비율은 작고, 링크 수가 적은 사이트(꼭짓점)의 비율은 크다. 수학적으로 다음과 같이 쓸 수 있습니다.

여기서 는 특정 정도의 꼭짓점 비율, 는 꼭짓점의 차수, 는 웹 그래프의 꼭짓점 수와 무관한 상수입니다. 사이트(정점)를 추가하거나 제거하는 과정에서 변경되지 않습니다.

이 거듭제곱 법칙은 생물학적 네트워크에서 은행 간 네트워크에 이르기까지 복잡한 네트워크에 보편적입니다.

인터넷은 전체적으로 사이트에 대한 무작위 공격에 저항합니다.

사이트의 파괴와 생성이 독립적으로 동일한 확률로 발생하기 때문에 확률이 1에 가까운 웹 그래프는 무결성을 유지하고 파괴되지 않습니다.

인터넷을 공부하려면 랜덤 그래프 모델을 구축해야 합니다. 이 모델은 실제 인터넷의 속성을 가져야 하며 너무 복잡하지 않아야 합니다.

이 문제는 아직 완전히 해결되지 않았습니다! 인터넷의 질적 모델을 구축하는 이 문제를 해결하면 정보 검색, 스팸 탐지 및 정보 보급을 향상시키는 새로운 도구를 개발할 수 있습니다.

생물학 및 경제 모델의 구성은 인터넷의 수학적 모델을 구성하는 작업보다 훨씬 일찍 시작되었습니다. 그러나 인터넷의 발전과 연구의 발전으로 이러한 모든 모델에 관한 많은 질문에 답할 수 있게 되었습니다.

인터넷 수학은 생물학자(박테리아 개체군의 성장 예측), 금융가(위기 위험) 등 많은 전문가에게 요구됩니다. 이러한 시스템에 대한 연구는 응용 수학 및 정보학의 중심 섹션 중 하나입니다.

그래프의 도움으로 무르만스크.

사람이 새로운 도시에 도착하면 일반적으로 주요 명소를 방문하는 것이 첫 번째 욕구입니다. 그러나 동시에 예약 시간이 제한되어 있는 경우가 많고 출장의 경우에는 매우 적습니다. 따라서 사전에 관광 계획을 세울 필요가 있습니다. 그리고 그래프는 경로를 구축하는 데 도움이 될 것입니다!

예를 들어, 처음으로 공항에서 무르만스크에 도착하는 전형적인 경우를 생각해 보십시오. 다음 명소를 방문할 예정입니다.

1. 물 위의 구세주의 해양 정교회;

2. 성 니콜라스 대성당;

3. 해양 수족관

4. 고양이 Semyon 기념비;

5. 핵 쇄빙선 레닌;

6. 무르만스크의 공원 조명;

7. 파크 밸리 오브 컴포트;

8. 콜라 다리

9. 무르만스크 해운 회사 역사 박물관;

10. 다섯 모서리의 정사각형;

11. 해상 무역항

먼저 이러한 장소를 지도에 배치하고 명소 간의 위치와 거리를 시각적으로 표시합니다. 도로망이 상당히 발달되어 있어 차량 이동이 어렵지 않을 것입니다.

지도의 명소(왼쪽)와 결과 그래프(오른쪽)는 부록 #1의 해당 그림에 나와 있습니다. 따라서 새로 온 사람은 먼저 콜라 다리 근처를 지나갈 것입니다(원하는 경우 다리를 앞뒤로 건널 수 있음). 그런 다음 그는 무르만스크의 빛의 공원과 안락의 계곡에서 휴식을 취하고 더 멀리 갈 것입니다. 결과적으로 최적의 경로는 다음과 같습니다.

그래프의 도움으로 여론 조사를 수행하는 계획을 시각화할 수도 있습니다. 부록 #2에 예제가 나와 있습니다. 이러한 답변에 따라 응답자는 다른 질문을 받습니다. 예를 들어, 사회학적 설문조사 1번에서 응답자가 수학이 과학 중 가장 중요하다고 생각하는 경우 물리 수업에 자신감을 느끼는지 묻습니다. 그가 달리 생각한다면, 두 번째 질문은 수요에 관한 것입니다. 인문학. 이러한 그래프의 꼭짓점은 질문이고 모서리는 답입니다.

2.3. 문제 해결에 그래프 이론 적용

그래프 이론은 수학, 생물학, 컴퓨터 과학과 같은 많은 주제 영역의 문제를 해결하는 데 사용됩니다. 그래프 이론을 이용하여 문제를 푸는 원리를 연구하고 연구 주제에 대해 스스로 문제를 구성했습니다.

작업 번호 1.

졸업생 모임에서 5명의 동급생이 악수를 나눴습니다. 총 몇 번의 악수를 했습니까?

솔루션: 급우를 그래프 정점으로 표시합니다. 각 정점을 다른 4개의 정점에 선으로 연결합니다. 우리는 10개의 라인을 얻었습니다. 이것은 악수입니다.

답: 10번의 악수(각 라인은 1번의 악수를 의미합니다).

작업 번호 2.

집 근처에있는 마을의 할머니는 포플러, 오크, 단풍 나무, 사과, 낙엽송, 자작 나무, 산 애쉬 및 소나무와 같은 8 그루의 나무를 자랍니다. 마가목은 낙엽송보다 높고 사과는 단풍나무보다 높고 참나무는 자작나무보다 낮지만 소나무보다 높고 소나무는 마가목보다 높고 자작나무는 포플러보다 낮고 낙엽송은 사과보다 높다. 나무는 높이가 높은 것에서 낮은 것 순으로 어떤 순서로 배열됩니까?

해결책:

트리는 그래프의 정점입니다. 원의 첫 글자로 표시합니다. 낮은 나무에서 높은 나무로 화살표를 그려 봅시다. 산 애쉬가 낙엽송보다 높으면 낙엽송에서 산 애쉬로 화살표를 놓고 자작 나무는 포플러보다 낮고 포플러에서 자작 나무로 화살표를 넣는 등입니다. 가장 낮은 나무가 단풍나무이고 그 다음이 사과, 낙엽송, 산재, 소나무, 참나무, 자작나무, 포플러인 것이 분명한 그래프를 얻습니다.

답변: 단풍나무, 사과, 낙엽송, 마가목, 소나무, 참나무, 자작나무 및 포플러.

작업 번호 3.

엄마는 2개의 봉투(일반 및 공기)와 3개의 우표(정사각형, 직사각형 및 삼각형)가 있습니다. 엄마는 아빠에게 편지를 보낼 봉투와 우표를 몇 가지 방법으로 고를 수 있습니까?

답: 6가지 방법

작업 번호 4.

사이 정착 A, B, C, D, E 도로가 건설됩니다. 길이를 결정해야 합니다 최단거리점 A와 E 사이. 도로를 따라 이동할 수만 있으며 길이는 그림에 표시되어 있습니다.

작업 번호 5.

세 명의 급우 - Maxim, Kirill 및 Vova는 스포츠에 참여하기로 결정하고 스포츠 섹션 선택을 통과했습니다. 1명의 남학생이 농구부에 지원했고 3명은 하키를 하고 싶어했던 것으로 알려졌다. Maxim은 1개 섹션에서만 시도했고 Kirill은 3개 섹션 모두에서, Vova는 2개 섹션에서 시도했습니다. 어떤 스포츠 섹션에서 소년 중 누구를 선택했습니까?

솔루션: 문제를 해결하기 위해 그래프를 사용합니다.

농구 맥심

축구 키릴

하키 보바

이후로 농구화살표가 하나만 있으면 Cyril이 섹션으로 이동했습니다. 농구. 그러면 Cyril은 연주하지 않을 것입니다. 하키, 에서 의미 하키이 섹션에 대해서만 오디션을 본 Maxim이 섹션을 선택한 경우 Vova는 축구 선수.

작업 번호 6.

일부 교사의 질병으로 인해 학교의 교장은 다음 상황을 고려하여 적어도 하루 동안 학교 일정의 일부를 작성해야 합니다.

1. 생명안전교사는 마지막 수업만 하기로 동의한다.

2. 지리 교사는 두 번째 또는 세 번째 수업을 제공할 수 있습니다.

3. 수학자는 첫 번째 수업만 하거나 두 번째 수업만 할 준비가 되어 있습니다.

4. 물리 교사는 첫 번째, 두 번째 또는 세 번째 수업을 할 수 있지만 한 수업에서만 가능합니다.

모든 교사가 만족할 수 있도록 학교의 교장은 어떤 일정을 작성할 수 있습니까?

솔루션: 이 문제는 가능한 모든 옵션을 정렬하여 해결할 수 있지만 그래프를 그리면 더 쉽습니다.

1. 1) 물리학 2. 1) 수학 3. 1) 수학

2) 수학 2) 물리학 2) 지리

3) 지리 3) 지리 3) 물리학

4) OBZH 4) OBZH 4) OBZH

결론

본 연구에서는 그래프 이론을 구체적으로 연구하였으며, 그래프 연구는 논리적 문제 해결에 도움이 될 수 있다는 가설을 입증하였으며, 다양한 과학 분야의 그래프 이론을 고려하여 7개 과제를 정리하였다.

학생들에게 문제에 대한 해결책을 찾도록 가르칠 때 그래프를 사용하면 학생들의 그래픽 기술을 향상시키고 일부는 선으로 연결된 유한한 점 집합의 특수 언어와 추론을 연결할 수 있습니다. 이 모든 것이 학생들에게 생각하는 법을 가르치는 일에 기여합니다.

능률 학습 활동사고력의 발달은 수학 문제를 해결하는 학생들의 창의적 활동 정도에 크게 좌우됩니다. 따라서 학생들의 정신 활동을 강화할 수 있는 수학 과제와 연습이 필요합니다.

학교의 과외 활동에서 과제의 적용과 그래프 이론 요소의 사용은 정확히 학생들의 정신 활동을 향상시키는 것을 목표로합니다. 우리 연구의 실용적인 자료가 수학의 과외 수업에서 유용할 수 있다고 믿습니다.

따라서 연구 작업의 목적이 달성되고 과제가 해결됩니다. 앞으로도 계속 그래프 이론을 연구하고 자체 루트를 개발할 계획입니다. 기억에 남는 장소무르만스크.

중고문헌 목록

Berezina L. Yu. "그래프와 그 응용"-M .: "계몽", 1979

Gardner M. "수학적 여가", M. "Mir", 1972

가드너 M. « 수학 퍼즐및 엔터테인먼트", M. "미르", 1971

Gorbachev A. "올림피아드 문제 모음" - M. MTsNMO, 2005

Zykov A. A. 그래프 이론의 기초. - M .: "대학 책", 2004. - S. 664

Kasatkin V. N. "수학의 특이한 문제", 키예프, "Radyan의 학교", 1987

수학적 구성 요소 / 편집자-컴파일러 N.N. Andreev, S.P. 코노발로프, N.M. 파뉴슈킨. - M.: 재단 "수학 연습" 2015 - 151 p.

Melnikov O. I. "그래프 이론의 재미있는 문제", Mn. 테트라시스템즈, 2001년

멜니코프 O.I. 그래프의 나라, 아무것도 모르는 학생을 위한 안내서. 에드. 3, 고정관념. M.: KomKniga, 2007. - 160p.

Olehnik S. N., Nesterenko Yu. V., Potapov M. K. "오래된 오락 문제", M. "Nauka", 1988

Ore O. "그래프 및 응용 프로그램", M. "Mir", 1965

Harari F. 그래프 이론 / 영어 번역. 그리고 서문. V.P. 코지레바. 에드. G. P. 가브릴로바. 에드. 2번째. - M.: 사설 URSS, 2003. - 296 p.

부록 №1

주요 명소 방문을 위한 최적의 일정 만들기

그래프의 도움으로 무르만스크.

최적의 경로는 다음과 같습니다.

8. 콜라 다리6. 무르만스크의 공원 조명7. 파크 밸리 오브 컴포트 2. 성 니콜라스 대성당10. 파이브 코너즈 스퀘어5. 핵 쇄빙선 레닌9. 무르만스크 해운 회사 역사 박물관11. 해상 무역 항구1. 물 위의 구세주의 해양 정교회4. 고양이 기념비 Semyon3. 수족관.

무르만스크 관광 안내

부록 №2

사회 조사 No.1, 2

그래프 방식이란?

수학에서 "그래프"라는 단어는 여러 점이 그려진 그림을 의미하며 그 중 일부는 선으로 연결되어 있습니다. 우선, 논의 할 백작은 과거의 귀족과 아무 관련이 없다는 것을 말할 가치가 있습니다. 우리의 "그래프"는 "나는 쓴다"를 의미하는 그리스어 "grapho"에서 파생되었습니다. "그래프", "전기"라는 단어에서 같은 뿌리.

수학에서 그래프 정의그래프는 유한한 점의 집합이며 그 중 일부는 선으로 연결되어 있습니다. 점을 그래프의 꼭짓점이라고 하고 연결선을 가장자리라고 합니다.

"분리된" 꼭짓점으로 구성된 그래프 다이어그램을 제로 그래프. (그림 2)

가능한 모든 간선이 만들어지지 않은 그래프를 호출합니다. 불완전한 차트. (그림 3)

가능한 모든 간선이 만들어진 그래프를 호출합니다. 완전한 그래프. (그림 4)

모든 정점이 다른 모든 정점의 모서리에 연결된 그래프를 호출합니다. 완벽한.

전체 그래프에 n개의 꼭짓점이 있으면 가장자리의 수는 다음과 같습니다.

n(n-1)/2

실제로, n개의 꼭짓점이 있는 완전한 그래프의 에지의 수는 그래프의 모든 n개의 에지 점으로 구성된 정렬되지 않은 쌍의 수로 정의됩니다.

불완전한 그래프는 누락된 간선을 추가하여 꼭짓점이 동일한 완전한 그래프로 완성할 수 있습니다. 예를 들어, 그림 3은 5개의 꼭짓점이 있는 불완전한 그래프를 보여줍니다. 그림 4에서 그래프를 완전한 그래프로 변환하는 모서리는 다른 색상으로 표시되며 이러한 모서리가 있는 그래프 정점 집합을 그래프의 보수라고 합니다.

꼭짓점의 각도 및 가장자리 수 계산.

그래프 정점에서 나오는 가장자리의 수를 꼭짓점 정도. 차수가 홀수인 그래프의 꼭짓점을 이상한, 그리고 짝수 학위 조차.

그래프의 모든 꼭짓점의 차수가 같을 때 그래프를 호출합니다. 동종의. 따라서 완전한 그래프는 동질적입니다.

그림 5

그림 5는 5개의 꼭짓점이 있는 그래프를 보여줍니다. 정점 A의 차수는 St.A로 표시됩니다.

그림에서: St.A = 1, St.B = 2, St.C = 3, St.G = 2, St.D = 0.

특정 그래프에 내재된 몇 가지 패턴을 공식화해 보겠습니다.

규칙성 1.

완전한 그래프의 꼭짓점의 차수는 같으며, 각 꼭짓점은 이 그래프의 꼭짓점 개수보다 1 작습니다.

증거:

이 패턴은 완전한 그래프를 고려한 후에 분명합니다. 각 꼭짓점은 자신을 제외한 모든 꼭짓점에 간선으로 연결됩니다. 즉, n-1개의 간선이 n개의 꼭짓점이 있는 그래프의 각 꼭짓점에서 나오므로 증명해야 합니다.

패턴 2.

그래프의 꼭짓점 차수의 합은 그래프 가장자리 수의 두 배와 같은 짝수입니다.

이 패턴은 전체 그래프뿐만 아니라 모든 그래프에도 유효합니다. 증거:

실제로 각 그래프 가장자리는 두 정점을 연결합니다. 이것은 그래프의 모든 꼭짓점의 각도 수를 더하면 각 모서리가 두 번 계산되었으므로 모서리 수 2R(R은 그래프의 모서리 수)의 두 배를 얻습니다. 입증하다

모든 그래프의 홀수 꼭짓점의 개수는 짝수입니다. 증거:

임의의 그래프 G를 고려하십시오. 이 그래프에서 차수가 1인 꼭짓점의 수를 K1과 같게 둡니다. 차수가 2인 꼭짓점의 수는 K2와 같습니다. ...; 차수가 n인 꼭짓점의 수는 Kn입니다. 그러면 이 그래프의 꼭짓점 차수의 합은 다음과 같이 쓸 수 있습니다.
K1 + 2K2 + ZK3 + ... + nKn.
반면에 그래프의 모서리 수가 R이면 규칙성 2에서 그래프의 모든 꼭짓점의 차수의 합이 2R임을 알 수 있습니다. 그러면 평등을 쓸 수 있습니다.
K1 + 2K2 + ZK3 + ... + nKn = 2R. (하나)
등식의 왼쪽에서 그래프의 홀수 정점 수와 동일한 합계를 선택합니다(K1 + K3 + ...).
K1 + 2K2 + ZK3 + 4K4 + 5K5 + ... + nK = 2R,
(K1 + K3 + K5 +...) + (2K2 + 2X3 +4K4 + 4K5 + ...)=2R
두 번째 괄호는 짝수의 합인 짝수입니다. 결과 합계(2R)는 짝수입니다. 따라서 (K1 + K3 + K5 +...)는 짝수입니다.

이제 그래프를 사용하여 해결된 문제를 고려하십시오.

작업. 클래스 챔피언십 . 탁구 클래스 챔피언십에는 Andrey, Boris, Viktor, Galina, Dmitry 및 Elena의 6명의 참가자가 있습니다. 챔피언십은 라운드 로빈 방식으로 진행됩니다. 각 참가자는 서로 한 번씩 플레이합니다. 현재까지 일부 게임이 이미 플레이되었습니다. Andrey는 Boris, Galina 및 Elena와 함께 했습니다. Boris는 이미 언급했듯이 Andrey와 Galina와 함께합니다. Victor - Galina, Dmitry 및 Elena와 함께; Andrey와 Boris가 있는 Galina; Dmitry - Victor와 Elena와 함께 - Andrey와 Victor와 함께. 지금까지 플레이한 게임은 몇 개이고 남은 게임은 몇 개입니까?

논의. 이러한 작업을 다이어그램 형태로 묘사해 보겠습니다. Andrey - 점 A, Boris - 점 B 등의 점으로 참가자를 나타냅니다. 두 명의 참가자가 이미 서로를 플레이했다면, 우리는 그들을 나타내는 포인트를 세그먼트로 연결할 것입니다. 그림 1과 같은 회로가 나옵니다.

점 A, B, C, D, E, E는 그래프의 정점으로 그래프의 가장자리인 세그먼트로 연결됩니다.

그래프 모서리의 교차점은 정점이 아닙니다.

지금까지 플레이한 게임의 수는 가장자리의 수와 같습니다. 7.

혼동을 피하기 위해 그래프의 꼭짓점은 종종 점이 아니라 작은 원으로 표시됩니다.

플레이해야 하는 게임의 수를 찾기 위해 같은 꼭짓점을 가진 또 다른 그래프를 만들지만 아직 서로 플레이하지 않은 참가자를 가장자리로 연결합니다(그림 2). 이 그래프에는 8개의 가장자리가 있습니다. 8 게임이 남아 있음을 의미합니다. Andrey - Victor 및 Dmitry와 함께; 보리스 - 빅터, 드미트리, 엘레나 등과 함께

다음 문제에서 설명한 상황에 대한 그래프를 작성해 보겠습니다.

작업 . 누가 Lyapkin - Tyapkin을합니까? 학교 연극 동아리는 고골의 국정원을 상연하기로 했다. 그리고 뜨거운 논쟁이 벌어졌다. 모든 것이 Lyapkin-Tyapkin에서 시작되었습니다.

Lyapkin - 내가 Tyapkin이 될 것이다! - 결연히 Gena를 선언했다.

아니요, 저는 Lyapkin이 될 것입니다 - Tyapkin, Dima는 반대했습니다. - 어렸을 때부터 이 이미지를 무대에서 구현하는 것이 꿈이었습니다.

글쎄, 그들이 내가 Khlestakov를 연기하게한다면이 역할을 포기하는 것이 좋습니다. - Gena는 관대함을 보여주었습니다.

- ... 그리고 나에게 - Osip, - Dima는 관대하게 그에게 굴복하지 않았습니다.

나는 Strawberry 또는 Gorodnichiy가되고 싶다 - Vova가 말했습니다.

아니, 내가 시장이 될거야. - Alik와 Borya가 한 목소리로 외쳤다. - 또는 클레스타코프, -

출연자들이 만족할 수 있도록 역할 분담이 가능할까?

논의. 맨 위 줄의 원에 젊은 배우를 묘사합시다 : A - Alik, B - Boris, C - Vova, G - Gena, D - Dima, 그리고 그들이 할 역할 - 두 번째 줄의 원 (1 - Lyapkin - Tyapkin, 2 - Khlestakov, 3 - Osip, 4 - 딸기, 5 - Gorodnichiy). 그런 다음 각 참가자로부터 세그먼트를 그립니다. 갈비뼈, 그가 하고 싶은 역할. 10개의 꼭짓점과 10개의 모서리가 있는 그래프를 얻습니다(그림 3).

문제를 해결하려면 공통 정점이 없는 10개 모서리 중 5개 모서리를 선택해야 합니다. 쉽게 생각해. 한 모서리가 정점 D와 B에서 각각 정점 3과 정점 4로 연결된다는 점에 유의하면 됩니다. 즉, Osip(정점 3)은 Dima(누가?)가, Vova는 Strawberry를 연기해야 합니다. Vertex1 - Lyapkin - Tyapkin -은 Edge로 G와 D로 연결됩니다. Edge 1 - D는 포기합니다. Dima가 이미 사용 중이므로 1 - G가 남아 있고 Lyapkin - Tyapkin은 Gena가 플레이해야 합니다. Khlestakov와 Gorodnichy의 역할에 해당하는 정점 A와 B를 정점 2와 5로 연결하는 것이 남아 있습니다. 이것은 두 가지 방법으로 수행할 수 있습니다. 가장자리 A -5 및 B - 2 또는 가장자리 A -2 및 B -5를 선택합니다. 첫 번째 경우에는 Alik이 Gorodnichiy를, Borya는 Khlestakov를, 두 번째 경우에는 그 반대의 경우도 마찬가지입니다. 그래프에서 알 수 있듯이 문제에는 다른 솔루션이 없습니다.

다음 문제를 풀면 동일한 그래프를 얻을 수 있습니다.

작업. 심술궂은 이웃들. 다섯 집의 주민들은 서로 다투었고 우물에서 만나지 않기 위해 우물을 나누어 각 집의 주인이 "그의"길을 따라 "그의" 우물로 가도록 결정했습니다. 그들은 그것을 할 수 있습니까?

질문이 생깁니다.분석된 문제에 그래프가 정말로 필요했는가?순전히 논리적인 방법으로 해결책에 도달하는 것이 가능하지 않습니까? 그래 넌 할수있어. 그러나 그래프는 조건 가시성을 제공하고 솔루션을 단순화하며 작업의 유사성을 보여 두 작업을 하나로 바꾸었습니다. 이제 그래프에 100개 이상의 꼭짓점이 있는 문제를 상상해 보십시오. 그러나 현대 엔지니어와 경제학자들이 해결해야 하는 것은 바로 그러한 작업입니다. 여기에서는 그래프 없이는 할 수 없습니다.

III. 오일러 그래프.

그래프 이론은 비교적 젊은 과학입니다. 뉴턴 시대에는 그래프의 종류인 "가계도"가 사용되었지만 그러한 과학은 아직 존재하지 않았습니다. 그래프 이론에 대한 첫 번째 작업은 Leonhard Euler에 속하며 1736년 St. Petersburg Academy of Sciences의 출판물에 나타났습니다. 이 작업은 다음과 같은 문제를 고려하여 시작되었습니다.

ㅏ) Königsberg 교량의 문제. Koenigsberg(지금의 Kaliningrad)시는 Pregel(Pregoli) 강의 은행과 두 개의 섬에 위치하고 있으며 도시의 다른 부분은 그림과 같이 7개의 다리로 연결되어 있습니다. 일요일에는 마을 사람들이 도시를 산책합니다. 각 다리를 한 번만 통과하고 경로의 시작점으로 돌아오는 경로를 선택할 수 있습니까?
이 문제의 해결을 고려하기 전에 " 오일러 그래프.

그림 4에 표시된 그래프에 동그라미를 쳐봅시다. 한 획에, 즉 종이에서 연필을 떼지 않고 선의 같은 부분을 두 번 이상 지나치지 않습니다.

이 그림은 외형이 매우 단순해 흥미로운 특징이 있습니다. 정점 B에서 움직이기 시작하면 분명히 성공할 것입니다. 그리고 우리가 상단 A에서 움직이기 시작하면 어떻게 될까요? 이 경우 선에 동그라미를 치는 데 실패했는지 확인하는 것은 쉽습니다. 우리는 항상 통과하지 않은 가장자리를 갖게 되며 이미 도달하는 것이 불가능합니다.

무화과에. 5는 한 획으로 그리는 방법을 알고 있는 그래프를 보여줍니다. 이것은 별입니다. 이전 그래프보다 훨씬 복잡해 보이지만 임의의 정점에서 시작하여 원을 그릴 수 있습니다.

도 6에 도시된 그래프는 한 번의 펜 스트로크로도 그릴 수 있다.

이제 그림을 그려보십시오. 한 획에도 7에 도시된 그래프

당신은 그것을하지 못했습니다! 왜요? 필요한 피크를 찾을 수 없습니까? 아니다! 그것에 관한 것이 아닙니다. 이 그래프는 펜으로 전혀 그릴 수 없습니다.

이것을 확신할 수 있는 주장을 해보자. 노드 A를 고려하십시오. 노드 A에서 세 개의 정점이 나옵니다. 이 꼭짓점에서 그래프를 그리기 시작하겠습니다. 이 각 모서리를 따라 가려면 꼭지점 A를 그 중 하나를 따라 떠나야 하며, 어느 시점에서 두 번째 모서리를 따라 정점 A로 돌아가서 세 번째 모서리를 따라 종료해야 합니다. 하지만 다시 로그인할 수 없습니다! 이것은 정점 A에서 그리기 시작하면 끝낼 수 없다는 것을 의미합니다.

이제 정점 A가 시작이 아니라고 가정합시다. 그런 다음 그리는 과정에서 가장자리 중 하나를 따라 입력하고 다른 가장자리를 따라 종료하고 세 번째 가장자리를 따라 다시 돌아와야 합니다. 그리고 우리는 그것을 벗어날 수 없기 때문에이 경우 상단 A가 끝이어야합니다.

따라서 정점 A는 도면의 시작 또는 끝 노드여야 합니다.

그러나 그래프의 다른 세 꼭짓점에 대해서도 마찬가지입니다. 그러나 결국 그림의 초기 정점은 하나의 정점일 수 있고 최종 정점도 하나의 정점일 수 있습니다! 이것은 이 그래프를 한 번에 그리는 것이 불가능하다는 것을 의미합니다.

종이에서 연필을 떼지 않고도 그릴 수 있는 그래프를 오일러 (그림 6).

이러한 그래프는 과학자 Leonhard Euler의 이름을 따서 명명되었습니다.

패턴 1. (우리가 고려한 정리에서 따릅니다).

홀수 개의 꼭짓점으로 그래프를 그리는 것은 불가능합니다.
패턴 2.

그래프의 모든 정점이 짝수이면 연필을 종이에서 들어 올리지 않고("한 획으로") 각 가장자리를 따라 한 번만 그리면 이 그래프를 그립니다. 이동은 모든 정점에서 시작하여 같은 정점에서 끝낼 수 있습니다.
패턴 3.

두 개의 홀수 꼭짓점만 있는 그래프는 종이에서 연필을 떼지 않고도 그릴 수 있으며, 움직임은 이 홀수 꼭짓점 중 하나에서 시작하여 두 번째 꼭짓점에서 끝나야 합니다.
패턴 4.

홀수 정점이 3개 이상인 그래프는 한 획에 그릴 수 없습니다.
종이에서 연필을 떼지 않고 그릴 수 있는 도형(그래프)을 유니커설이라고 합니다.

카운트가 호출됩니다 연결된,정점 중 두 개를 경로, 즉 일련의 모서리로 연결할 수 있는 경우 각 모서리는 이전 모서리의 끝에서 시작합니다.

카운트가 호출됩니다 일관성 없는, 이 조건이 충족되지 않으면.

그림 7 그림 8

그림 7은 분명히 연결이 끊긴 그래프를 보여줍니다. 예를 들어 그림에서 꼭짓점 D와 E 사이에 모서리를 그리면 그래프가 연결됩니다. (그림 8)

그래프 이론에서 이러한 간선(그래프가 연결에서 연결 해제로 전환되는 제거 후)을 호출합니다. 다리.

그림 7에서 브리지의 예는 각각 그래프의 "분리된" 부분의 정점을 연결하는 가장자리 DE, A3, VZh 등이 될 수 있습니다(그림 8).

연결이 끊긴 그래프는 여러 "조각"으로 구성됩니다. 이러한 "조각"은 연결 구성 요소그래프. 각 연결된 구성 요소는 물론 연결된 그래프입니다. 연결된 그래프에는 연결된 구성 요소가 하나 있습니다.
정리.

그래프는 연결되어 있고 최대 두 개의 홀수 정점이 있는 경우에만 오일러입니다.

증거:

시작과 끝을 제외한 모든 꼭짓점에 대한 그래프를 그려서 떠나는 횟수만큼 들어갑니다. 따라서 2개를 제외한 모든 정점의 차수는 짝수여야 합니다. 즉, 오일러 그래프에는 최대 2개의 홀수 정점이 있습니다.

이제 Königsberg 교량 문제로 돌아가 보겠습니다.

문제 토론 . A, B, C, D 문자로 도시의 다른 부분을 지정하고 문자 a, b, c, d, e, f, g로 도시의 해당 부분을 연결하는 다리로 지정합시다. 이 문제에서는 다리를 건너는 것 만 있습니다. 다리를 건너면 항상 도시의 한 부분에서 다른 부분으로 이동하고 반대로 도시의 한 부분에서 다른 부분으로 이동할 때 확실히 건너 뛸 것입니다. 다리. 따라서 A, B, C, D(그림 8)의 정점이 도시의 개별 부분을 나타내고 모서리 a, b, c, d, e가 있는 그래프 형태로 도시 계획을 묘사합니다. , f, g는 도시의 해당 부분을 연결하는 다리입니다. 가장자리는 종종 직선 세그먼트가 아니라 곡선 세그먼트("호")로 묘사하는 것이 더 편리합니다.

문제의 조건을 충족하는 경로가 있는 경우 이 그래프의 닫힌 연속 순회가 있고 각 모서리를 따라 한 번씩 통과합니다. 즉, 이 그래프는 한 획으로 그려야 합니다. 그러나 이것은 불가능합니다. 원래 정점으로 선택하는 정점에 관계없이 나머지 정점과 동시에 각 "들어오는"가장자리 (우리가이 부분에 들어간 다리)를 통과해야합니다. city)는 다리의 "나가는" 가장자리에 해당하며, 이를 사용하여 도시의 이 부분을 떠나게 됩니다. 각 꼭짓점에서 수렴하는 가장자리의 총 개수는 짝수여야 합니다. 우리 그래프는 이 조건을 만족하지 않으므로 필요한 경로가 존재하지 않습니다.