그래프 이론



그래프 이론(문화어: 그라프리론, graph理論, 영어: graph theory;圖論,도론)은 수학에서 객체 간에 짝을 이루는 관계를 모델링하기 위해 사용되는 수학 구조인 그래프에 대한 연구이다. 이 문맥에서 그래프는 꼭짓점(버텍스/vertex), 교점(노드/node), 점(포인트/point)으로 구성되며 이것들은 (엣지/edge, 간선), 즉 선으로 연결된다. 그래프는 무향(무방향성)일 수 있는데 이는 각 변(선)으로 연결되는 두 개의 꼭짓점 간에 구별이 없다는 의미이며, 한편 변은 한 꼭짓점에서 다른 꼭짓점 간에 방향이 있을 수도 있다. (더 자세한 정의와 이러한 유형의 그래프의 변종에 대해서는 그래프 이론 용어를 참고할 것) 그래프는 이산수학의 주요 논제 가운데 하나이다.

그래프 이론의 기초적인 정의에 대해서는 그래프 이론 용어를 참고할 것.

목차

정의


그래프 이론의 정의는 다양하다. 아래에 그래프 및 관련 수학 구조들을 정의하는 더 기초적인 방법들 중 일부를 나열한다.

그래프

가장 일반적인 의미에서[1] 그래프(graph)는 순서쌍 G = (V, E)으로 볼 수 있으며, 여기에서 집합 V는 꼭짓점, E는 간선(변)을 의미한다. 혼동을 피하기 위해, 이러한 형태의 그래프는 정확히 방향이 없으며(무향), 단순한 그래프라고 기술할 수 있다.

주요 개념


그래프꼭짓점 과 2개의 꼭짓점을 연결하는 으로 구성되어 있다. 변의 길이나 꼭짓점의 위치 따위는 중요하지 않으므로, 그래프는 조합론적인 대상이다.

그래프 이론의 연구 대상은 그래프 및 추가 구조를 갖춘 그래프이다.

그래프들은 또한 각종 국소적 구조들을 갖는다. 그래프의 국소적 구조의 예로는 다음을 들 수 있다.

이러한 구조들을 가지고 그래프들을 분류할 수 있다.

그래프 이론에서는 이러한 개념 및 성질들 사이의 관계를 연구한다.

분야


그래프 이론의 주요 분야는 다음과 같다.

역사


그래프 이론의 시초는 레온하르트 오일러가 1736년에 쓴 쾨니히스베르크의 다리 문제에 대한 논문으로 여겨진다. 이 논문에서, 오일러는 그래프한붓그리기 존재 여부에 대한 간단한 필요충분조건을 제시하였다. 오일러의 다면체 정리오귀스탱 루이 코시[2]시몽 앙투안 장 륄리에[3]에 의해 연구되고 일반화되었으며, 위상수학의 시초를 상징한다.

19세기에, 수학·물리학의 각종 분야에서 그래프의 개념이 등장하기 시작하였다.

이러한 문제들을 풀기 위해, 율리우스 페테르센(덴마크어: Julius Petersen, 1839~1910) · 앨프리드 켐프(영어: Alfred Kempe, 1849~1922) · 쾨니그 데네시(1884~1944) · 조지 데이비드 버코프(1884~1944) · 해슬러 휘트니(1907~1989) · 윌리엄 토머스 텃(1917~2002) 등은 그래프 이론의 기초적인 개념 및 정리들을 정립하였다. 쾨니그는 1936년에 그래프 이론에 대한 최초의 책을 출판하였다.

현재, 그래프 이론은 활발한 연구 주제로 남아 있다. 비교적 최근의 주요 연구 결과로는 케네스 아펠과 볼프강 하켄의 4색 정리의 증명 (1976년), 강한 완벽 그래프 정리의 증명 (2002년) 등이 있다.

그래프 그림


그래프 이론 데이터 구조


참고 문헌


같이 보기


각주


  1. See, for instance, Iyanaga and Kawada, 69 J, p. 234 or Biggs, p. 4.
  2. Cauchy, A. L. (1813), "Recherche sur les polyèdres - premier mémoire", [[:fr:Journal de l'École polytechnique|]], 9 (Cahier 16): 66–86.
  3. L'Huillier, S.-A.-J. (1812–1813), "Mémoire sur la polyèdrométrie", Annales de Mathématiques, 3: 169–189.

외부 링크





분류: 그래프 이론


데이트: 15.03.2021 10:39:22 CET

출처: Wikipedia (저자들 [역사])    Lizenz: CC-by-sa-3.0

변화들: 모든 그림과 그와 관련된 대부분의 디자인 요소가 제거되었습니다. 일부 아이콘은 이미지로 대체되었습니다. 일부 템플릿이 제거되거나 (예 : "문서 확장 필요) 할당되었습니다. CSS 클래스가 제거되거나 조화되었습니다.
기사 또는 카테고리로 연결되지 않는 위키백과 특정 링크 (예 : "레드 링크", "편집 페이지 링크", "포털 링크")는 제거되었습니다. 모든 외부 링크에는 추가 이미지가 있습니다. 약간의 디자인 변경 외에도 미디어 컨테이너,지도, 내비게이션 상자 및 음성 버전이 제거되었습니다.

부디 을 알아차리다 주어진 콘텐츠는 주어진 시점에 위키백과에서 자동으로 가져 오기 때문에 수동 확인이 가능했고 불가능했습니다. 따라서 kowiki.org는 획득 한 콘텐츠의 정확성과 실제 성을 보장하지 않습니다. 현재 잘못된 정보 나 부정확 한 표시가있는 정보가있는 경우 언제든지 문의하기: 이메일.
또한보십시오: 법적 고지 & 개인 정보 정책.