그래프 이론이란 무엇이며 그래프는 어떻게 정의됩니까?

1736년, 스위스의 물리학자이자 수학자인 Leonhard Euler(1707-1783)의 연구에 기초하여, 정점의 연속이 다음을 정의하는 것이 관찰되었습니다. 그러나 경로가 반복되는 가장자리 없이 다른 꼭짓점으로 구성된 경우 경로 또는 경로라고 합니다. 오일리안; 추가로 각 모서리를 한 번만 횡단하여 시작점에 도달하면 오일러 주기(회로)가 있습니다.

견적(APA)

알렉산더 바라자 | 7월 2022
물리학 학위

그 부분에서 우리는 그래프를 순서쌍으로 정의합니다. (가서) 어디 V 그래프의 모든 정점 또는 노드의 (비어 있지 않은) 집합을 지정하는 반면 ㅏ 그래프의 꼭짓점을 연결하는 모든 모서리 또는 선의 집합(비어 있을 수 있음)을 지정합니다. 세트의 요소 ㅏ v와 w는 요소(노드 또는 꼭짓점)인 순서 없는 쌍 {v, w}로 지정할 수 있습니다. V, 이런 식으로 v와 w는 인접한 정점이라고 합니다(가장자리로 연결됨).

그래프 이론은 7개의 다리를 건너는 방법을 궁금해하는 대중적 독창성 문제에 오일러가 제시한 답에서 비롯됩니다. 쾨니히스베르그 공동체의 두 섬(당시 독일의 일부, 현재 러시아의 칼리닌그라드)에 합류하여 두 섬을 사용하지 않고 본토와 연결 시간에 관계없이 동일한 다리와 출발점(본토에 위치)에 도착하는 시간이 무엇이든 간에, 이 경우에는 궁극적으로 할 수 있었다.

쾨니히스베르크의 7개 다리 문제

오일러는 Königsberg를 그래프로 모델링했습니다. 여기서 각 점(정점 또는 노드)은 다리를 나타내고 각 선(가장자리)은 육지의 경로를 나타냅니다.

이 문제에 대한 해결책은 무엇입니까?

하나도 없다 해결책 오일러가 보여준 것처럼 정점의 차수가 짝수가 아니므로 부과된 조건을 충족합니다. 즉, 짝수의 선이 각 점에 영향을 미치지 않습니다. _[3]. 이렇게 간단하게 정의된 구조로 많은 것을 할 수 있는 것 같지는 않지만 다음과 같은 경우가 종종 있습니다. 수학, 때로는 사물이 보이는 것과 다릅니다. 따라서 가장 다작, 횡단 및 학제 간 영역 중 하나 _[4] 인간 지식의 그래프 이론.

오일러 그래프 또는 오일러 궤적?

다음 그래프에는 모두 오일러 경로가 있습니다. _[5]. 그들은 모두 오일러 주기를 가지고 있습니까?

세 번째 그래프를 살펴보겠습니다.

꼭짓점에 번호를 매기자.

그러면 시퀀스 {3,4,6,2,1,3,7,6,5,4,2}에 의해 정의된 경로가 오일러 ​​경로임을 알 수 있습니다. 간선을 반복하지 않고 전체 그래프를 통과하지만 시작점에 도달하지 않기 때문에 오일러 순환이 아닙니다. 정점 번호를 다르게 지정했다면 어떻게 되었을까요? 이제 경로가 다른 계승에 의해 정의된다는 점을 제외하면 많지 않습니다. 초기 솔루션에서 제안한 것과 다른 경로를 따랐다면 어떻게 되었을까요? 이 질문은 대답하기가 조금 더 복잡하며 소프트웨어 엔지니어가 일반적으로 좋아하는 알고리즘이 포함됩니다. 프로그램 작성.

여기에 노출된 내용에 대한 보다 엄격한 증거를 보려면 다음 결과를 참조해야 합니다.

"~이다 G 연결된 그래프 _[6]. 그럼 네 G 가지고있다 회로 오일러, 각 꼭짓점의 차수는 짝수인 반면, G 오일러 경로가 있고 G에는 홀수 차수의 꼭짓점이 정확히 두 개 있습니다. _[7] (정확히 경로가 시작되고 끝나는 정점)".

그런 다음 실제로 우리가 취하는 그래프에서 꼭짓점 3과 6만 홀수 차수를 가지고 있음을 확인할 수 있습니다. 정점의 번호가 다른 경우에도 발생), 따라서 해당 그래프에는 경로가 있습니다 오일리안 _[8]. 나머지 그래프에 대해 유사한 방식으로 진행할 수 있으며 실제로 경로와 오일러 주기 또는 다른 말로 하면 연필을 들고 반복하지 않고 그러한 그래프를 그릴 수 있습니까? 윤곽? 이 질문에 대한 답은 지금까지 설명한 내용에서 추론할 수 있지만 소근육 운동 능력, 독창성 및 인내의 관점에서 흥미로운 점으로 독자에게 6 이상의 그래프를 찾아 그리도록 초대합니다. 정점 궤도 오일러.

다른 유형의 그래프가 있습니까? 그래프 이론이 '실제' 세계에 적용됩니까?

우리가 매우 간략하게 검토한 이 그래프는 그래프 이론에서 찾을 수 있는 여러 유형의 그래프 중 하나일 뿐입니다. 우리는 또한 요소가 계층 구조 및 계산 계산 및 계산 및 계산으로 분류될 수 있는 집합에서 매우 대표적인 나무와 같은 그래프를 찾을 수 있습니다. 개연성_[9], 이중 그래프, 해밀턴 그래프 _[10], 등.

Psycho.의 그래픽 모델 및 네트워크 이미지, Ruiz, Ana María.

이러한 수수께끼는 오늘날의 세계에서 다음과 같은 다양한 상황에서 엄청난 적용 가능성을 가지고 있습니다. 생물학 분자 _[11], 컴퓨팅_[12], 통신 _[13] 및 네트워크 분석 _[14]. 그렇다면 다음과 같이 물어볼 가치가 있습니다. 거의 모든 문제가 평범한 수학의 가장 흥미롭고 눈에 띄는 결과 중 하나가 될 것입니까? 아마도 이를 위해서는 인류의 가장 저명한 정신 중 한 사람의 공헌이 필요했을 것입니다.