그래프 이론

수학에서, 그래프 이론(graph theory)은 객체 간의 쌍방향 관계를 모형화하는 데 사용되는 수학적 구조인 그래프를 연구하는 학문이다.이 컨텍스트의 그래프는 모서리(링크 또는 선이라고도 함)로 연결된 정점(노드 또는 점이라고도 함)으로 구성됩니다.가장자리가 두 정점을 대칭으로 링크하는 무방향 그래프와 가장자리가 두 정점을 비대칭으로 링크하는 방향 그래프를 구분합니다.그래프는 이산 수학의 주요 연구 대상 중 하나이다.

정의들

그래프 이론의 정의는 다양합니다.다음은 그래프와 관련된 수학적 구조를 정의하는 보다 기본적인 방법 중 몇 가지입니다.

그래프

세 개의 정점과 세 개의 모서리가 있는 그래프입니다.

제한적이지만 매우 일반적인 용어의 ^[1]^[2]한 가지 의미에서 그래프는 다음 구성 요소로 구성된 $G=(V,E)$ $G=(V,E)$ 쌍 G $G=(V,E)$ ( $G=(V,E)$ V $G=(V,E)$ , $G=(V,E)$ ) { $displaystyle$ G= ( $V,$ E $)}$ 입니다.

$(\displaystyle$ V $V$ 정점 세트(노드 또는 점이라고도 함)
$E\subseteq \{\{x,y\}\mid x,y\in V\;{\textrm {and}}\;x\neq y\}$ E $E\subseteq \{\{x,y\}\mid x,y\in V\;{\textrm {and}}\;x\neq y\}$ { $E\subseteq \{\{x,y\}\mid x,y\in V\;{\textrm {and}}\;x\neq y\}$ , y $E\subseteq \{\{x,y\}\mid x,y\in V\;{\textrm {and}}\;x\neq y\}$ 、 $E\subseteq \{\{x,y\}\mid x,y\in V\;{\textrm {and}}\;x\neq y\}$ , $E\subseteq \{\{x,y\}\mid x,y\in V\;{\textrm {and}}\;x\neq y\}$ 、 $E\subseteq \{\{x,y\}\mid x,y\in V\;{\textrm {and}}\;x\neq y\}$ 、 $E\subseteq \{\{x,y\}\mid x,y\in V\;{\textrm {and}}\;x\neq y\}$ 、 y $E\subseteq \{\{x,y\}\mid x,y\in V\;{\textrm {and}}\;x\neq y\}$ x xx $x$ xx y xx y xx yx $、 y$ \ $mid$ x , y \ mid x , y \ in V \ ; { \ textrm { and $E\subseteq \{\{x,y\}\mid x,y\in V\;{\textrm {and}}\;x\neq y\}$ } \ $;$ x \ $neq$ y \} $E\subseteq \{\{x,y\}\mid x,y\in V\;{\textrm {and}}\;x\neq y\}$ 、 is ( ( ( ( of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of

모호함을 피하기 위해 이러한 유형의 객체를 정확히 무방향 단순 그래프라고 할 수 있습니다.

$\{x,y\}$ { $\{x,y\}$ , y $}$ { $displaystyle$ $\{x,y\}$ \ { $x$ , y $x$ \ $\{x,y\}$ } $\{x,y\}$ 에서는 $꼭지점$ x $와$ y를 $y$ 엣지의 엔드 포인트라고 부릅니다.가장자리는 $x$ 와 $x$ $y와$ $x$ 하고 $x$ 와 $x$ $y$ 에 $x$ 한다고 합니다. 정점은 그래프에 존재하며 모서리에 속하지 않을 수 있습니다 $y$ 위의 정의에 따라 허용되지 않는 여러 모서리는 동일한 두 정점을 연결하는 둘 이상의 모서리입니다.

다중 ^[3]^[4]에지를 허용하는 한 가지 일반적인 의미에서 그래프는 다음 요소로 구성된 순서 $G=(V,E,\phi )$ G $G=(V,E,\phi )$ ( $G=(V,E,\phi )$ , $G=(V,E,\phi )$ , $G=(V,E,\phi )$ ) $G=(V,E,\phi )$ { $displaystyle$ G = ( $V$ , $E$ , \ $phi$ ) $G=(V,E,\phi )$ }입니다 $G=(V,E,\phi )$ .

$(\displaystyle$ V $V$ 정점 세트(노드 또는 점이라고도 함)
$E$ \ $displaystyle$ E \ $E$ 엣지 세트(링크 또는 라인이라고도 함);
$x$ $E\to \{x,y\}\mid$ x $,y\in$ V $\;{\textrm {and}\;x\neq$ y $\phi :E\to \{\{x,y\}\mid x,y\in V\;{\textrm {and}}\;x\neq y\}$ 각 에지를 순서가 없는 정점 쌍에 매핑하는 입사 함수입니다(즉, 에지는 2개의 다른 정점과 관련지어집니다).

애매함을 피하기 위해 이런 유형의 오브젝트를 정확히 무방향 멀티그래프라고 부를 수 있습니다.

루프는 정점을 연결하는 가장자리입니다.위의 두 가지 정의에 정의된 그래프에는 루프가 있을 수 없습니다. 왜냐하면 $정점$ x(\ $displaystyle$ x)를 $x$ 연결하는 루프는 가장자리(무방향 단순 그래프의 경우 $\{x,x\}=\{x\}$ 이거나 {x, x $\{x,x\}=\{x\}$ $\{\{x,y\}\mid x,y\in V\;{\textrm {and}}\;x\neq y\}$ { $\{x,x\}=\{x\}$ $\{\{x,y\}\mid x,y\in V\;{\textrm {and}}\;x\neq y\}$ { $x$ $\{\{x,y\}\mid x,y\in V\;{\textrm {and}}\;x\neq y\}$ {displaystyle $\{x$ ,x\} { $\{\{x,y\}\mid x,y\in V\;{\textrm {and}}\;x\neq y\}$ $x\}$ $\{\{x,y\}\mid x,y\in V\;{\textrm {and}}\;x\neq y\}$ { $\{\{x,y\}\mid x,y\in V\;{\textrm {and}}\;x\neq y\}$ 에 $\{x,x\}=\{x\}$ 포함되지 않은 에 입사하기 때문입니다. $\displaystyle \{x,y\}\mid$ x $,y\in$ V $\;{\textrm {and}\;x\neq$ y $\{\{x,y\}\mid x,y\in V\;{\textrm {and}}\;x\neq y\}$ 루프를 허용하려면 정의를 확장해야 합니다.무방향 단순 그래프의 경우 E $(\$ $displaystyle$ E $)$ 의 $E$ $E$ 를 E $E\subseteq \{\{x,y\}\mid x,y\in V\}$ x , $E\subseteq \{\{x,y\}\mid x,y\in V\}$ } $E\subseteq \{\{x,y\}\mid x,y\in V\}$ x , $E\subseteq \{\{x,y\}\mid x,y\in V\}$ V $E\subseteq \{\{x,y\}\mid x,y\in V\}$ }(\ $displaystyle$ E $\subseteq \{x$ , $y\}\mid$ x , $y\in$ V $E\subseteq \{\{x,y\}\mid x,y\in V\}$ 로 $E\subseteq \{\{x,y\}\mid x,y\in V\}$ 해야 합니다.무방향 멀티그래프 $\phi$ 의 경우, \ $phy\$ displaystyle ": $E\to \{x,y\}\mid$ x $,y\in$ V $\phi :E\to \{\{x,y\}\mid x,y\in V\}$ 애매함을 피하기 위해 이러한 유형의 오브젝트는 각각 루프를 허용하는 무방향 단순 그래프와 루프를 허용하는 무방향 다중 그래프(때로는 무방향 유사 문자)라고 불립니다 $.$

$V$ {\ $displaystyle$ V $}$ 와 $V$ E{\ $displaystyle$ E $}$ 는 $E$ 일반적으로 유한한 것으로 간주되며, 무한 그래프에 대해서는 잘 알려진 결과 중 많은 부분이 사실이 아니거나 다소 다릅니다. 왜냐하면 많은 인수가 무한 케이스에서 실패하기 때문입니다.또한 V{\ $displaystyle$ V $}$ 는 $V$ 비어 있지 않은 것으로 $E$ 되지만 E{\ $displaystyle$ E $}$ 는 $E$ 비어 있는 집합으로 허용됩니다.그래프의 순서는 $|V|$ { $style$ V $|V|$ 정점 수입니다.그래프의 크기는 E $|E|$ {\ $style$ E $|E|$ 이며 모서리 수입니다.정점의 정도 또는 원자가는 정점에 입사하는 가장자리 수로, 루프가 두 번 카운트됩니다.그래프의 정도는 꼭지점 각도의 최대값입니다.

순서 n의 무방향 단순 그래프에서 각 정점의 최대 정도는 n - 1이고 그래프의 최대 크기는 n(n - 1)/2이다.

루프를 $G$ 하는무방향 단순 그래프의 $가장자리$ 는 $G$ $G$ 의정점에 대칭적인 균질 관계를 유도합니다 $G$ G의 $G$ 정점에서는 $G$ 의 $인접$ 관계라고 합니다.구체적으로는 각 가장자리 $($ , y )에 대해 x, y $(x,y)$ 그 $(x$ $, y$ 에 대해 x, display $style$ $x}$ 와 $x$ y ${displaystyle$ y $}$ 는 $y$ 서로 인접해 있다고 합니다 $.$ x { $displaystyle$ x } $x$ ~ $y$ { $displaystyle$ y $}$ 。

유향 그래프

3개의 정점과 4개의 방향 모서리가 있는 방향 그래프(쌍방향 화살표는 각 방향의 모서리를 나타냅니다).

방향 그래프 또는 이중 그래프는 모서리가 방향을 갖는 그래프입니다.

제한적이지만 매우 일반적인 용어에서 ^[5]방향 그래프는 다음 요소로 구성된 순서 $G=(V,E)$ G $G=(V,E)$ ( $G=(V,E)$ , $E$ ) { $displaystyle$ G= ( $V,$ E $)}$ 입니다 $G=(V,E)$ .

$(\displaystyle$ V $V$ 정점 세트(노드 또는 점이라고도 함)
$E\subseteq \left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}$ E $E\subseteq \left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}$ { ( $E\subseteq \left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}$ , $E\subseteq \left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}$ ) $E\subseteq \left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}$ （ $E\subseteq \left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}$ x , $E\subseteq \left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}$ ） $E\subseteq \left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}$ $E\subseteq \left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}$ $E\subseteq \left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}$ $E\subseteq \left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}$ x xx $E\subseteq \left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}$ y $}$ { $display style$ E \ $subseteq \ left$ \ { x , $y$ ) \ $mid$ ( $x$ , $y$ ) \ $in$ V^ { } \ ; { \ $textrongright$ } \ ;x $E\subseteq \left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}$ \ $neq$ y \ \, of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of

모호함을 피하기 위해 이러한 유형의 객체를 정확히 방향성 단순 그래프라고 할 수 있습니다.

x $(x$ $,$ $y$ $)$ 에서 y $(x,y)$ $displaystyle$ x $y$ 로 $x$ 향하는 엣지( $x, y)$ 에서 $(x,y)$ $꼭지점$ (\ $displaystyle$ x)와 $x$ y(\ $displaystyle$ y $)$ 는 $y$ 엣지의 끝점, $(\displaystyle$ x)는 $x$ 엣지의 끝점,y(\ $displaystyle$ y $)$ 는 $y$ head로 불립니다.가장자리는 $x$ 와 $x$ $y와$ $x$ 하고 $x$ 와 $x$ $y$ 에 $x$ 한다고 합니다. 정점은 그래프에 존재하며 모서리에 속하지 않을 수 있습니다 $y$ $(y,x)$ , $x$ ) { $displaystyle ($ $(x,y)$ , $(x,y)$ ) { $displaystyle$ ( $x$ , $(x,y)$ y $(x,y)$ 의 $(y,x)$ $(x,y)$ 반전 엣지라고 불립니다.위의 정의에 따라 여러 엣지는 동일한 꼬리와 동일한 헤드를 가진 둘 이상의 엣지입니다.

다중 ^[5]에지를 허용하는 용어의 또 다른 일반적인 의미에서 방향 그래프는 다음을 포함하는 순서 $G=(V,E,\phi )$ $G=(V,E,\phi )$ G $G=(V,E,\phi )$ ( $G=(V,E,\phi )$ , $G=(V,E,\phi )$ , $G=(V,E,\phi )$ ) { $displaystyle$ G = ( $V$ , $E$ , \ $phi$ ) }입니다.

$(\displaystyle$ V $V$ 정점 세트(노드 또는 점이라고도 함)
$E$ \ $displaystyle$ E \ $E$ 엣지 세트(유향 에지, 유향 링크, 유향 라인, 화살표 또는 호라고도 함)
$}$ E $\to$ \ $left\{(x,y)\mid(x,y)\in$ V $^{2}\;{\textrm {and}}\;x\neq y\$ right $\phi :E\to \left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}$ 는 모든 에지를 순서 있는 정점의 쌍에 매핑하는 입사 함수입니다(즉, 에지는 2개의 다른 정점과 관련지어집니다).

애매함을 피하기 위해 이런 유형의 오브젝트를 정확히 유향 멀티그래프라고 부를 수 있습니다.

루프는 정점을 연결하는 가장자리입니다.위의 두 가지 정의에 정의된 방향 그래프에는 루프가 있을 수 없습니다. $x$ 는 정점x(\ $displaystyle$ $(x,x)$ x)를 $x$ 결합하는 루프가 가장자리(유향 단순 그래프의 경우)이거나 $\left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}$ (유향 멀티그래프의 경우 $)$ { ( $\left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}$ $(x,x)$ $\left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}$ ) $\left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}$ }(x $\left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}$ , $\left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}$ ) $\left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}$ $\left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}$ x x 2 $\left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}$ x x x x x x ∈ $\left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}$ ∈ $\left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}$ and directed $(x,x)$ directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed directed $\displaystyle \left\{(x,y)\mid(x,y)\in$ V $^{2}\;{\textrm {and}}\;x\neq$ y $\right$ 루프를 허용하려면 정의를 확장해야 합니다. $\phi$ 한 유도 그래프의 경우 E $(\$ $E\subseteq \left\{(x,y)\mid (x,y)\in V^{2}\right\}$ E $)$ $E$ 를 $E$ E( $E\subseteq \left\{(x,y)\mid (x,y)\in V^{2}\right\}$ , y $E\subseteq \left\{(x,y)\mid (x,y)\in V^{2}\right\}$ ) $（$ x $E\subseteq \left\{(x,y)\mid (x,y)\in V^{2}\right\}$ , $E\subseteq \left\{(x,y)\mid (x,y)\in V^{2}\right\}$ ） $E\subseteq \left\{(x,y)\mid (x,y)\in V^{2}\right\}$ { $displaystyle$ E \ subseteq \ $left$ \ { x , $y )$ $\ mid$ ( $x$ , $y$ ) \ $in V^$ { $2$ \ right $E\subseteq \left\{(x,y)\mid (x,y)\in V^{2}\right\}$ } 로 $E\subseteq \left\{(x,y)\mid (x,y)\in V^{2}\right\}$ 해야 합니다 $.$ $}$ $E\to \left\{(x,y)\mid(x,y)\in$ V $^{2}\right$ 모호성을 피하기 위해 이러한 유형의 오브젝트는 루프를 허용하는 유향 단순 그래프(또는 루프를 허용하는 유향 멀티 그래프)라고 할 수 있습니다.

$루프$ G $(Displaystyle$ G $)$ 를 $G$ 허용하는 방향성 단순 그래프의 엣지는 G $($ $Displaystyle$ G $G$ )의 정점에서의 동질관계로, G $(Displaystyle$ G $G$ 의 인접관계라고 불린다.구체적으로는 각 $(x,y)$ 엣지( $x, y$ 에 대해 그 $($ $y$ , y), ${\displaystyle$ y $}$ 는 서로 $y$ 인접해 있으며 x $\displaystyle$ x $}$ $x$ $y$ $\displaystyle$ y로 $x$ 됩니다.

적용들

2013년 ^[6]여름 한 달 동안 Wikipedia 편집자(편집자)가 서로 다른 Wikipedia 언어 버전(수직)에 기여한 네트워크 그래프.

그래프는 물리적,^[9] 생물학적,^[7]^[8] 사회적 및 정보 시스템에서 다양한 유형의 관계와 프로세스를 모델링하는 데 사용할 수 있습니다.많은 현실적인 문제들이 그래프로 표현될 수 있다.실제 시스템에 대한 적용을 강조하면서, 네트워크라는 용어는 때때로 속성(예: 이름)이 정점과 모서리에 관련지어지는 그래프를 의미하며, 실제 시스템을 네트워크로 표현하고 이해하는 주제를 네트워크 과학이라고 한다.

컴퓨터 공학

데이터 구조라고 알려진 컴퓨터 과학 분야는 통신, 데이터 구성, 계산 장치, 계산 흐름 등의 네트워크를 나타내기 위해 그래프를 사용합니다.예를 들어 웹 사이트의 링크 구조는 정점이 웹 페이지를 나타내고 방향 엣지가 한 페이지에서 다른 페이지로 링크를 나타내는 방향 그래프로 나타낼 수 있다.소셜 미디어,^[10] 여행, 생물학, 컴퓨터 칩 설계, 신경 변성 ^[11]^[12]질환의 진행 상황 지도 작성, 그리고 많은 다른 분야의 문제에 대해서도 비슷한 접근법을 취할 수 있습니다.따라서 그래프를 다루는 알고리즘의 개발은 컴퓨터 과학에서 큰 관심사이다.그래프의 변환은 종종 공식화되고 그래프 개서 시스템에 의해 표현됩니다.그래프의 규칙 기반 메모리 내 조작에 초점을 맞춘 그래프 변환 시스템을 보완하는 것은 트랜잭션 안전, 그래프 구조화 데이터의 지속적인 저장 및 쿼리에 맞춰진 그래프 데이터베이스이다.

언어학

자연어가 종종 분리된 구조에 잘 적응하기 때문에 다양한 형태의 그래프 이론 방법은 언어학에서 특히 유용하다는 것이 입증되었습니다.전통적으로 구문과 구성 의미론은 계층형 그래프에서 모델링된 구성 원리에 있는 표현력을 가진 나무 기반 구조를 따릅니다.헤드 구동 구문 구문 문법과 같은 보다 현대적인 접근법은 비순환형 그래프인 유형화된 특징 구조를 사용하여 자연어의 구문을 모델링합니다.어휘 의미론에서, 특히 컴퓨터에 적용되는 것과 같이, 주어진 단어가 관련된 단어로 이해될 때 단어 의미를 모델링하는 것이 더 쉽다. 그러므로 의미 네트워크는 계산 언어학에서 중요하다.그러나 음운론(예: 격자 그래프를 사용하는 최적성 이론)과 형태론(예: 유한 상태 형태학, 유한 상태 변환기를 사용하는 것)의 다른 방법은 그래프로서의 언어 분석에서 일반적이다.실제로 언어학에 대한 이 수학 영역의 유용성은 TextGraphs와 같은 조직과 WordNet, VerbNet과 같은 다양한 'Net' 프로젝트를 만들어 왔습니다.

물리 화학

그래프 이론은 또한 화학과 물리학의 분자를 연구하는 데 사용된다.응축물리학에서 복잡한 시뮬레이션 원자구조의 3차원 구조는 원자의 위상에 관련된 그래프 이론 특성에 관한 통계를 수집함으로써 정량적으로 연구할 수 있다.또 파인만 그래프와 계산규칙은 ^[13]양자장이론을 이해하고 싶은 실험 숫자에 근접한 형태로 요약하고 있다.화학에서 그래프는 분자의 자연 모형을 만들며, 여기서 꼭지점은 원자와 모서리 결합을 나타냅니다.이 접근법은 화학 편집기에서 데이터베이스 검색까지 분자 구조의 컴퓨터 처리에 특히 사용됩니다.통계물리학에서 그래프는 시스템의 상호작용하는 부분들 사이의 국소적 연결과 그러한 시스템에서의 물리적 과정의 역학을 나타낼 수 있다.마찬가지로 컴퓨터 신경과학 그래프는 다양한 인지 과정을 일으키기 위해 상호작용하는 뇌 영역 간의 기능적 연결을 나타내기 위해 사용될 수 있다. 여기서 정점은 뇌의 다른 영역을 나타내고 가장자리는 이들 영역 간의 연결을 나타낸다.그래프 이론은 전기 네트워크의 전기 모델링에 중요한 역할을 합니다.여기서 가중치는 네트워크 ^[14]구조의 전기적 특성을 얻기 위해 와이어 세그먼트의 저항과 관련지어집니다.그래프는 다공질 매체의 마이크로 스케일 채널을 나타내기 위해서도 사용됩니다.여기서 정점은 기공을 나타내고 가장자리는 기공을 연결하는 작은 채널을 나타냅니다.화학 그래프 이론은 분자 그래프를 분자를 모형화하는 수단으로 사용합니다.그래프와 네트워크는 위상 전이 및 임계 현상을 연구하고 이해하기 위한 훌륭한 모델입니다.노드 또는 엣지를 제거하면 네트워크가 작은 클러스터로 분할되어 위상 천이로 연구되는 중대한 전환이 발생합니다.이 분류는 침투 ^[15]이론을 통해 연구된다.

사회과학

사회학에서의 그래프 이론:Moreno Sociogram(1953)^[16]

그래프 이론은 또한 사회학에서 배우의 명성을 측정하거나, 특히 소셜 네트워크 분석 소프트웨어를 사용하여 루머 확산을 탐구하는 방법으로 널리 사용된다.소셜 네트워크의 산하에 많은 다른 종류의 ^[17]그래프가 있다.지인관계와 우정 그래프는 사람들이 서로를 알고 있는지 여부를 나타냅니다.영향 그래프는 특정 사람이 다른 사람의 행동에 영향을 미칠 수 있는지 여부를 모델링합니다.마지막으로 콜라보레이션 그래프는 두 사람이 함께 영화 속에서 연기하는 것과 같이 특정한 방식으로 함께 작업하는지 여부를 모델링합니다.

생물학

마찬가지로, 그래프 이론은 정점이 특정 종이 존재하는(또는 서식하는) 지역을 나타낼 수 있고 가장자리가 영역 간의 이동 경로 또는 이동을 나타낼 수 있는 생물학 및 보존 노력에 유용합니다.이 정보는 번식 패턴을 보거나 질병, 기생충의 확산을 추적할 때 또는 이동의 변화가 다른 종에 어떻게 영향을 미칠 수 있는지를 추적할 때 중요하다.

그래프는 분자 생물학 및 유전체학에서도 복잡한 관계를 가진 데이터 세트를 모델링하고 분석하는 데 일반적으로 사용된다.예를 들어, 그래프 기반 방법은 종종 단일 셀 문자 변환 분석에서 셀을 함께 '클러스터링'하기 위해 사용됩니다.또 다른 용도는 경로에서 유전자 또는 단백질을 모델링하고 대사 경로와 유전자 조절 ^[18]네트워크와 같은 그들 사이의 관계를 연구하는 것입니다.유전자 발현 패턴의 진화적 트리, 생태 네트워크 및 계층적 클러스터링도 그래프 구조로 표현된다.

그래프 이론은 또한 ^[19]커넥토믹스에도 사용된다; 신경계는 그래프로 볼 수 있다. 여기서 노드는 뉴런이고 가장자리는 그들 사이의 연결이다.

수학

수학에서 그래프는 기하학과 매듭 이론과 같은 토폴로지의 특정 부분에서 유용합니다.대수 그래프 이론은 그룹 이론과 밀접한 관련이 있다.대수 그래프 이론은 동적 시스템과 복잡성을 포함한 많은 분야에 적용되어 왔다.

기타 토픽

그래프의 각 모서리에 가중치를 할당함으로써 그래프 구조를 확장할 수 있다.가중치가 있는 그래프 또는 가중치가 있는 그래프는 쌍으로 연결된 연결에 몇 가지 숫자 값이 있는 구조를 나타내기 위해 사용됩니다.예를 들어, 그래프가 도로망을 나타내는 경우 가중치는 각 도로의 길이를 나타낼 수 있습니다.각 모서리에는 거리(앞의 예와 같이), 이동 시간 또는 금전적 비용 등 여러 가지 가중치가 관련될 수 있습니다.이러한 가중 그래프는 일반적으로 GPS와 비행 시간과 비용을 비교하는 여행 계획 검색 엔진을 프로그래밍하는 데 사용됩니다.

역사

쾨니히스베르크 다리 문제

레온하르트 오일러가 쾨니히스베르크의 일곱 다리에 대해 쓴 1736년에 발표된 논문은 그래프 ^[20]이론 역사상 최초의 논문으로 여겨진다.이 논문과 반데르몽드가 기사 문제에 대해 쓴 논문은 라이프니츠가 시작한 분석 시투스를 계속했다.볼록 다면체의 모서리, 꼭지점, 면의 수에 관한 오일러의 공식은 코시와 L'Huilier에 ^[22]의해^[21] 연구되고 일반화되었으며, 위상이라고 알려진 수학 분과의 시작을 나타냅니다.

오일러가 쾨니히스베르크의 다리에서 쓴 논문과 리스팅이 위상 개념을 도입한 지 1세기 이상 지난 후, 케일리는 특정한 종류의 그래프인 ^[23]나무를 연구하기 위해 미분적분학에서 발생하는 특정 분석 형태에 대한 관심이 주도되었다.이 연구는 이론 화학에 많은 영향을 끼쳤다.그가 사용한 기법은 주로 특정 특성을 가진 그래프의 열거와 관련이 있다.열거형 그래프 이론은 1935년에서 1937년 사이에 카일리의 결과와 풀랴에 의해 출판된 기본적인 결과로부터 생겨났다.이것들은 1959년 De Bruijn에 의해 일반화되었다.케일리는 나무에 대한 그의 결과를 화학 조성에 ^[24]대한 현대 연구와 연결시켰다.수학에서 나온 아이디어와 화학에서 나온 아이디어의 융합은 그래프 이론의 표준 용어의 일부가 된 것을 시작했다.

특히, "그래프"라는 용어는 실베스터가 1878년 네이처에 발표한 논문에서 도입되었는데, 그는 대수학 및 분자 다이어그램의 "^[25]양적 불변량"과 "공변량"을 유추합니다.

"…" 따라서 모든 불변량과 공변량은 케쿨레안 도표나 화학 도표와 정확히 동일한 그래프로 표현될 수 있다.[…] 그래프의 기하학적 곱셈, 즉 별도의 그래프가 주어진 변수 내 또는 공변수의 곱에 대한 그래프를 구성하기 위한 규칙을 제공한다.[…]" (원문과 같은 이탈리아어)

그래프 이론의 첫 번째 교과서는 Dénes Knnig에 의해 쓰여졌고 ^[26]1936년에 출판되었다.1969년에 출판된 프랭크 해러리의 또 다른 책은 "세계에서 이 ^[27]주제에 대한 결정적인 교과서"로 간주되어 수학자, 화학자, 전기 공학자와 사회 과학자가 서로 대화할 수 있게 되었다.Harary는 모든 로열티를 Pollya ^[28]Prize에 기부했다.

그래프 이론에서 가장 유명하고 자극적인 문제 중 하나는 네 가지 색상의 문제이다: "평면에 그려진 어떤 지도도 공통의 경계를 가진 어떤 두 지역이 다른 색을 가질 수 있는 방식으로 그 지역을 네 가지 색으로 칠할 수 있다는 것이 사실인가?"이 문제는 1852년 프란시스 거스리에 의해 처음 제기되었고, 그 첫 번째 기록은 같은 해 해 해밀턴에게 보낸 드 모건의 편지에 있다.케일리, 켐프, 그리고 다른 사람들의 증거를 포함하여 많은 잘못된 증거들이 제안되었다.Tait, Hewood, Ramsey 및 Hadwiger에 의한 이 문제의 연구와 일반화는 임의의 속(속)을 가진 표면에 내장된 그래프의 색채 연구를 이끌었다.타이트의 개혁은 특히 피터슨과 쾨니그에 의해 연구된 인수분해 문제라는 새로운 종류의 문제를 야기했다.1941년 투란이 얻은 색채와 더욱 특별한 결과에 대한 램지의 연구는 그래프 이론의 또 다른 분야인 극단 그래프 이론의 기원이었다.

4색 문제는 1세기 이상 해결되지 않은 채 남아 있었다.1969년에 Heesch는 ^[29]컴퓨터를 사용하여 문제를 해결하는 방법을 발표했다.케네스 아펠과 볼프강 하켄에 의해 1976년에 만들어진 컴퓨터 지원 증거는 ^[30]^[31]헤쉬에 의해 개발된 "배출" 개념을 근본적으로 사용한다.이 증명은 1,936개의 구성의 속성을 컴퓨터로 확인하는 것을 포함하고 있으며, 그 복잡성 때문에 당시에는 완전히 받아들여지지 않았습니다.불과 633개의 구성을 고려한 더 간단한 증거는 20년 후 Robertson, Seymour, Sanders 및 ^[32]Thomas에 의해 제시되었습니다.

1860년과 1930년의 위상학의 자율적 발전은 조던, 쿠라토스키, 휘트니의 작품을 통해 그래프 이론을 수정시켰다.그래프 이론과 위상학의 공통적인 발전의 또 다른 중요한 요소는 현대 대수학의 기술 사용에서 비롯되었다.이러한 사용의 첫 번째 예는 물리학자 구스타프 키르히호프의 연구에서 나온 것이다. 그는 1845년에 전기 회로의 전압과 전류를 계산하기 위한 키르히호프의 회로 법칙을 발표했다.

그래프 이론에서 확률론적 방법의 도입, 특히 그래프 연결의 점근 확률에 대한 Erdss와 Rényi의 연구에서, 무작위 그래프 이론으로 알려진 또 다른 분파가 생겨났고, 이는 그래프 이론 결과의 생산적인 원천이었다.

표현

그래프는 자연에서 나타나는 관계의 추상화이기 때문에 특정 표현과 결합할 수 없습니다.표현 방법은 그러한 표현이 특정 애플리케이션에 제공하는 편의성의 정도에 따라 달라집니다.가장 일반적인 표현은 정점이 그려지고 모서리로 연결되는 시각과 표의 행이 그래프 내의 정점 간의 관계에 대한 정보를 제공하는 표 형식입니다.

비주얼: 그래프 그리기

그래프는 일반적으로 모든 정점에 대해 점이나 원을 그리고 모서리에 의해 연결된 경우 두 정점 사이에 선을 그려 시각적으로 표현됩니다.그래프가 방향일 경우 화살표로 방향을 나타냅니다.그래프에 가중치가 있는 경우 가중치가 화살표에 추가됩니다.

그래프 도면을 구성하는 방법은 여러 가지가 있으므로 그래프 자체(추상적이고 비시각적인 구조)와 혼동해서는 안 됩니다.중요한 것은 정확한 레이아웃이 아니라 가장자리 수에 따라 어떤 정점이 어떤 정점에 연결되느냐입니다.실제로 두 도면이 동일한 그래프를 나타내는지 여부를 판단하기가 어려운 경우가 많습니다.문제 영역에 따라 다른 레이아웃보다 더 적합하고 이해하기 쉬운 레이아웃이 있을 수 있습니다.

W. T. Tutte의 선구적인 작업은 그래프 그리기 주제에 매우 큰 영향을 미쳤다.다른 업적들 중에서, 그는 그래프 도면을 얻기 위해 선형 대수법을 도입했다.

그래프 드로잉은 건널목 번호와 그 다양한 일반화를 다루는 문제를 포괄한다고도 할 수 있다.그래프의 교차 수는 평면의 그래프 도면에 포함되어야 하는 모서리 사이의 최소 교차 수입니다.평면 그래프의 경우 교차 수는 정의상 0입니다.평면 이외의 표면의 도면도 연구됩니다.

원 패킹, 교차 그래프 및 인접 행렬의 기타 시각화를 포함하여 꼭지점과 모서리에서 멀리 떨어진 그래프를 시각화하는 다른 기술이 있습니다.

표 형식: 그래프 데이터 구조

표 형식의 표현은 계산 어플리케이션에 적합하다.컴퓨터 시스템에 그래프를 저장하는 방법에는 여러 가지가 있습니다.사용되는 데이터 구조는 그래프 구조와 그래프 조작에 사용되는 알고리즘에 따라 달라집니다.이론적으로 리스트 구조와 매트릭스 구조를 구별할 수 있지만, 구체적인 적용에서 가장 좋은 구조는 종종 두 가지 모두를 조합한 것입니다.리스트 구조는 메모리 요건이 작기 때문에 스파스 그래프에 선호되는 경우가 많습니다.한편, 매트릭스 구조는 일부 애플리케이션에서 더 빠른 액세스를 제공하지만 대량의 메모리를 소비할 수 있습니다.현대의 병렬 컴퓨터 아키텍처에서 효율적인 희박한 매트릭스 구조의 구현은 현재 ^[33]조사의 대상이다.

리스트 구조에는 엣지 리스트, 정점 쌍의 배열 및 각 정점의 인접 리스트가 포함됩니다.이 리스트에는 엣지 리스트와 마찬가지로 각 정점에는 인접한 정점의 리스트가 있습니다.

행렬 구조는 행이 정점을 나타내며 열이 가장자리를 나타내는 0과 1의 행렬인 입사 행렬과 행과 열이 모두 정점에 의해 색인화되는 인접 행렬을 포함한다.두 경우 모두 1은 2개의 인접 객체를 나타내고 0은 2개의 비인접 객체를 나타냅니다.정도 행렬은 정점의 정도를 나타냅니다.라플라시안 행렬은 정점의 정도에 대한 정보를 포함하는 인접 행렬의 변형된 형태로, 그래프의 스패닝 트리 수에 대한 키르히호프의 정리 같은 계산에 유용합니다.거리행렬은 인접행렬과 마찬가지로 행과 열이 모두 정점에 의해 색인화되지만 각 셀에 0 또는 1을 포함하는 것이 아니라 두 정점 사이의 최단 경로 길이를 포함합니다.

문제

열거

그래픽 열거에 관한 많은 문헌이 있다. 즉, 지정된 조건을 충족하는 그래프를 계산하는 문제이다.이 작품들 중 일부는 Harary와 Palmer(1973년)에서 발견된다.

서브그래프, 유도 서브그래프 및 마이너

서브그래프 동형 문제라 불리는 일반적인 문제는 주어진 그래프에서 서브그래프로 고정된 그래프를 찾는 것이다.이러한 질문에 관심을 갖는 한 가지 이유는 많은 그래프 속성이 하위 그래프에 대해 유전되기 때문입니다. 즉, 그래프는 모든 하위 그래프에 해당 특성이 있는 경우에만 속성을 가집니다.불행히도, 특정 종류의 최대 서브그래프를 찾는 것은 종종 NP-완전한 문제입니다.예를 들어 다음과 같습니다.

가장 큰 완전한 서브그래프를 찾는 것을 clique 문제(NP-complete)라고 합니다.

서브그래프 동형사상의 한 가지 특별한 경우는 그래프 동형사상의 문제이다.두 그래프가 동형인지 여부를 묻습니다.이 문제가 NP-완전인지, 다항식 시간에 해결할 수 있는지는 알려지지 않았다.

유사한 문제는 주어진 그래프에서 유도된 하위 그래프를 찾는 것이다.다시, 일부 중요한 그래프 특성은 유도 하위 그래프와 관련하여 유전된다. 즉, 모든 유도 하위 그래프에 해당 특성이 있는 경우에만 그래프가 속성을 갖는다는 것을 의미한다.특정 종류의 최대 유도 서브그래프를 찾는 것도 종종 NP-완전이다.예를 들어 다음과 같습니다.

가장 큰 에지리스 유도 하위 그래프 또는 독립 집합을 찾는 것을 독립 집합 문제(NP-완전)라고 한다.

또 다른 문제인 사소한 격납문제는 주어진 그래프의 부차적인 고정그래프를 찾는 것이다.그래프의 마이너 또는 서브컨트랙션은 서브그래프를 사용하여 일부(또는 없음) 모서리를 축소하여 얻은 그래프입니다.많은 그래프 속성은 미성년자에 대해 세습됩니다. 즉, 모든 미성년자가 속성을 가지고 있는 경우에만 그래프가 속성을 가집니다.예를 들어, 바그너의 정리에는 다음과 같이 기술되어 있습니다.

완전 이분 그래프_3,3 K(3코티지 문제 참조) 또는 완전 그래프₅ K를 마이너로 포함하는 경우 그래프는 평면적이다.

유사한 문제인 세분 격납 문제는 주어진 그래프의 세분화로서 고정된 그래프를 찾는 것이다.그래프의 하위 분할 또는 동형성은 일부(또는 없음) 모서리를 세분화하여 얻은 그래프입니다.하위 구분 격납은 평면성과 같은 그래프 속성과 관련이 있습니다.예를 들어, 쿠라토프스키의 정리에는 다음과 같이 기술되어 있다.

그래프는 완전 이분_3,3 그래프 K도₅ 완전 그래프 K도 아닌 부분으로서 포함되는 경우 평면적이다.

하위 구분 격납의 또 다른 문제는 켈만이다.–시모어 추측:

평면이 아닌 모든 5-vertex 연결 그래프에는 5-vertex 전체 그래프₅ K의 하위 분할이 포함됩니다.

다른 종류의 문제는 다양한 종과 그래프의 일반화가 포인트 삭제 하위 그래프에 의해 결정되는 범위와 관련이 있다.예를 들어 다음과 같습니다.

재건축 추측

그래프 색칠

그래프 이론의 많은 문제와 정리들은 그래프를 색칠하는 다양한 방법과 관련이 있다.일반적으로 인접한 두 정점이 같은 색을 가지거나 다른 유사한 제한이 없도록 그래프에 색을 입히는 데 관심이 있습니다.또한 색상 가장자리(동일하는 두 가장자리가 같은 색이 되지 않도록 가능) 또는 기타 변형도 고려할 수 있습니다.그래프 색칠에 관한 유명한 결과와 추측은 다음과 같습니다.

4색 정리
강완전 그래프 정리
에르데스-파베르-로바시즈 추측(미해결)
베자드의 추측이라고도 불리는 총색소 추측(해결되지 않음)
목록 색상의 추측(해결되지 않음)
해드위거 추측(그래프 이론) (미해결)

전제 및 통일

제약조건 모델링 이론은 부분 차수로 관련된 방향 그래프 군과 관련이 있다.이러한 애플리케이션에서 그래프는 특수성에 따라 정렬됩니다. 즉, 더 구체적이고 따라서 더 많은 양의 정보를 포함하는 더 많은 제약이 있는 그래프가 더 일반적인 그래프에 포함된다는 것을 의미합니다.그래프 간 연산은 두 그래프(있는 경우) 간의 추정 관계의 방향 평가와 그래프 통합 계산을 포함한다.두 주장 그래프의 통합은 입력과 일치하는(즉, 모든 정보를 포함하는) 가장 일반적인 그래프(또는 그 계산)로 정의된다. 그러한 그래프가 존재할 경우, 효율적인 통합 알고리즘이 알려져 있다.

엄격히 구성된 제약 프레임워크에서 그래프 통합은 충분한 만족도와 결합 함수이다.잘 알려진 응용 프로그램에는 언어 구조의 정교함을 증명하고 모델링하는 자동 정리가 포함됩니다.

경로 문제

네트워크 흐름

특히 네트워크 흐름의 다양한 개념과 관련된 어플리케이션에서는 다음과 같은 많은 문제가 발생합니다.

최대 흐름 최소 컷 정리

가시성 문제

박물관 경비 문제

문제 해결

그래프에서 문제를 다루는 것은 정점/서브그래프의 하위 집합에서 다양한 집합 커버 문제를 나타낼 수 있습니다.

세트 문제는 세트 커버 문제의 특수한 경우로 세트가 닫힌 네이버입니다.
정점 커버 문제는 커버할 세트가 모든 모서리에 있는 세트 커버 문제의 특수한 경우입니다.
히트 세트라고도 불리는 원래 세트 커버 문제는 하이퍼그래프에서 정점 커버로 설명할 수 있습니다.

분해 문제

그래프의 가장자리 집합을 분할하는 것으로 정의되는 분해(분할의 각 부분의 모서리에 필요한 만큼의 정점을 포함)에는 매우 다양한 질문이 있습니다.종종, 문제는 그래프를 하위 그래프로 분해하는 것입니다. 예를 들어, 완전한 그래프를 해밀턴 사이클로 분해하는 것입니다.다른 문제는 주어진 그래프를 분해해야 하는 그래프 패밀리를 지정하거나, 완전한 그래프_n K를 각각 1, 2, 3, ..., n - 1의 가장자리를 가진 n - 1의 지정된 트리로 분해한다.

연구된 특정 분해 문제는 다음과 같습니다.

수목성(arboricity)은 가능한 한 적은 숲으로 분해됩니다.
Cycle Double Cover(사이클 이중 커버)는 각 모서리를 정확히 두 번 덮는 사이클 모음으로 분해됩니다.
가장자리 색칠, 가능한 한 적은 매칭으로 분해
그래프 인수분해: 정규 그래프를 주어진 도수의 정규 하위 그래프로 분해하는 방법

그래프 클래스

많은 문제는 다양한 그래프 클래스의 구성원을 특성화하는 것과 관련이 있다.이러한 질문의 예는 다음과 같습니다.

클래스의 멤버 열거
금지된 하위 구조의 관점에서 클래스 특성화
클래스 간의 관계 확인(예를 들어 그래프의 한 속성이 다른 속성을 의미하는지 여부)
클래스 멤버쉽을 결정하기 위한 효율적인 알고리즘 찾기
클래스 구성원에 대한 표현 찾기

「」를 참조해 주세요.

알고리즘

서브에리어

수학의 관련 영역

일반화

저명한 그래프 이론가

메모들

^ 벤더 & 윌리엄슨 2010, 페이지 148
^ 예를 들어, 이야나가와 카와다 69 J 페이지 234 또는 빅스 페이지 4를 보십시오.
^ 벤더 & 윌리엄슨 2010, 페이지 149
^ 예를 들면, Graham 등, 페이지 5를 참조해 주세요.
^ ^a ^b 벤더 & 윌리엄슨 2010, 페이지 161. 161
^ Hale, Scott A. (2013). "Multilinguals and Wikipedia Editing". Proceedings of the 2014 ACM Conference on Web Science - WebSci '14: 99–108. arXiv:1312.0976. Bibcode:2013arXiv1312.0976H. doi:10.1145/2615569.2615684. ISBN 9781450326223. S2CID 14027025.
^ Mashaghi, A.; et al. (2004). "Investigation of a protein complex network". European Physical Journal B. 41 (1): 113–121. arXiv:cond-mat/0304207. Bibcode:2004EPJB...41..113M. doi:10.1140/epjb/e2004-00301-0. S2CID 9233932.
^ Shah, Preya; Ashourvan, Arian; Mikhail, Fadi; Pines, Adam; Kini, Lohith; Oechsel, Kelly; Das, Sandhitsu R; Stein, Joel M; Shinohara, Russell T (2019-07-01). "Characterizing the role of the structural connectome in seizure dynamics". Brain. 142 (7): 1955–1972. doi:10.1093/brain/awz125. ISSN 0006-8950. PMC 6598625. PMID 31099821.
^ Adali, Tulay; Ortega, Antonio (May 2018). "Applications of Graph Theory [Scanning the Issue]". Proceedings of the IEEE. 106 (5): 784–786. doi:10.1109/JPROC.2018.2820300. ISSN 0018-9219.
^ Grandjean, Martin (2016). "A social network analysis of Twitter: Mapping the digital humanities community" (PDF). Cogent Arts & Humanities. 3 (1): 1171458. doi:10.1080/23311983.2016.1171458. S2CID 114999767.
^ Vecchio, F (2017). ""Small World" architecture in brain connectivity and hippocampal volume in Alzheimer's disease: a study via graph theory from EEG data". Brain Imaging and Behavior. 11 (2): 473–485. doi:10.1007/s11682-016-9528-3. PMID 26960946. S2CID 3987492.
^ Vecchio, F (2013). "Brain network connectivity assessed using graph theory in frontotemporal dementia". Neurology. 81 (2): 134–143. doi:10.1212/WNL.0b013e31829a33f8. PMID 23719145. S2CID 28334693.
^ Bjorken, J. D.; Drell, S. D. (1965). Relativistic Quantum Fields. New York: McGraw-Hill. p. viii.
^ Kumar, Ankush; Kulkarni, G. U. (2016-01-04). "Evaluating conducting network based transparent electrodes from geometrical considerations". Journal of Applied Physics. 119 (1): 015102. Bibcode:2016JAP...119a5102K. doi:10.1063/1.4939280. ISSN 0021-8979.
^ Newman, Mark (2010). Networks: An Introduction (PDF). Oxford University Press. Archived from the original (PDF) on 2020-07-28. Retrieved 2019-10-30.
^ 그랜드장, 마틴(2015).소셜 네트워크 분석 및 시각화: 모레노의 소시오그래픽이 다시 찾아왔다.Moreno(1934년), Who Shall Survive를 기반으로 네트워크를 재설계.
^ Rosen, Kenneth H. (2011-06-14). Discrete mathematics and its applications (7th ed.). New York: McGraw-Hill. ISBN 978-0-07-338309-5.
^ Kelly, S.; Black, Michael (2020-07-09). "graphsim: An R package for simulating gene expression data from graph structures of biological pathways". Journal of Open Source Software. The Open Journal. 5 (51): 2161. Bibcode:2020JOSS....5.2161K. bioRxiv 10.1101/2020.03.02.972471. doi:10.21105/joss.02161. ISSN 2475-9066. S2CID 214722561.
^ Shah, Preya; Ashourvan, Arian; Mikhail, Fadi; Pines, Adam; Kini, Lohith; Oechsel, Kelly; Das, Sandhitsu R; Stein, Joel M; Shinohara, Russell T (2019-07-01). "Characterizing the role of the structural connectome in seizure dynamics". Brain. 142 (7): 1955–1972. doi:10.1093/brain/awz125. ISSN 0006-8950. PMC 6598625. PMID 31099821.
^ Biggs, N.; Lloyd, E.; Wilson, R. (1986), Graph Theory, 1736-1936, Oxford University Press
^ Cauchy, A. L. (1813), "Recherche sur les polyèdres - premier mémoire", Journal de l'École Polytechnique, 9 (Cahier 16): 66–86.
^ L'Huillier, S.-A.-J. (1812–1813), "Mémoire sur la polyèdrométrie", Annales de Mathématiques, 3: 169–189.
^ Cayley, A. (1857), "On the theory of the analytical forms called trees", Philosophical Magazine, Series IV, 13 (85): 172–176, doi:10.1017/CBO9780511703690.046, ISBN 9780511703690
^ Cayley, A. (1875), "Ueber die Analytischen Figuren, welche in der Mathematik Bäume genannt werden und ihre Anwendung auf die Theorie chemischer Verbindungen", Berichte der Deutschen Chemischen Gesellschaft, 8 (2): 1056–1059, doi:10.1002/cber.18750080252.
^ Sylvester, James Joseph (1878). "Chemistry and Algebra". Nature. 17 (432): 284. Bibcode:1878Natur..17..284S. doi:10.1038/017284a0.
^ Tutte, W.T. (2001), Graph Theory, Cambridge University Press, p. 30, ISBN 978-0-521-79489-3, retrieved 2016-03-14
^ Gardner, Martin (1992), Fractal Music, Hypercards, and more…Mathematical Recreations from Scientific American, W. H. Freeman and Company, p. 203
^ Society for Industrial and Applied Mathematics (2002), "The George Polya Prize", Looking Back, Looking Ahead: A SIAM History (PDF), p. 26, archived from the original (PDF) on 2016-03-05, retrieved 2016-03-14
^ Heinrich Heesch: Untersuchungen zum Vierfarben 문제.만하임: 1969년 서지학 연구소.
^ Appel, K.; Haken, W. (1977), "Every planar map is four colorable. Part I. Discharging", Illinois J. Math., 21 (3): 429–490, doi:10.1215/ijm/1256049011.
^ Appel, K.; Haken, W. (1977), "Every planar map is four colorable. Part II. Reducibility", Illinois J. Math., 21 (3): 491–567, doi:10.1215/ijm/1256049012.
^ Robertson, N.; Sanders, D.; Seymour, P.; Thomas, R. (1997), "The four color theorem", Journal of Combinatorial Theory, Series B, 70: 2–44, doi:10.1006/jctb.1997.1750.
^ Kepner, Jeremy; Gilbert, John (2011). Graph Algorithms in the Language of Linear Algebra. SIAM. p. 1171458. ISBN 978-0-898719-90-1.

레퍼런스

Bender, Edward A.; Williamson, S. Gill (2010). Lists, Decisions and Graphs. With an Introduction to Probability.
Claude, Claude (1958). Théorie des graphes et ses applications. Paris: Dunod. 영어판, Wiley 1961; Methuen & Co, New York 1962; Russian, Moscow 1961; 스페인어, 멕시코 1962; Roumanian, Bucharest 1969; 중국어, 상하이 1963; 1962년 초판 영어판, 뉴욕 도버, 2001.
Biggs, N.; Lloyd, E.; Wilson, R. (1986). Graph Theory, 1736–1936. Oxford University Press.
Bondy, J. A.; Murty, U. S. R. (2008). Graph Theory. Springer. ISBN 978-1-84628-969-9.
Bollobás, Béla; Riordan, O. M. (2003). Mathematical results on scale-free random graphs in "Handbook of Graphs and Networks" (S. Bornholdt and H.G. Schuster (eds)) (1st ed.). Weinheim: Wiley VCH.
Chartrand, Gary (1985). Introductory Graph Theory. Dover. ISBN 0-486-24775-9.
Deo, Narsingh (1974). Graph Theory with Applications to Engineering and Computer Science (PDF). Englewood, New Jersey: Prentice-Hall. ISBN 0-13-363473-6.
Gibbons, Alan (1985). Algorithmic Graph Theory. Cambridge University Press.
Golumbic, Martin (1980). Algorithmic Graph Theory and Perfect Graphs. Academic Press.
Harary, Frank (1969). Graph Theory. Reading, Massachusetts: Addison-Wesley.
Harary, Frank; Palmer, Edgar M. (1973). Graphical Enumeration. New York, New York: Academic Press.
Mahadev, N. V. R.; Peled, Uri N. (1995). Threshold Graphs and Related Topics. North-Holland.
Newman, Mark (2010). Networks: An Introduction. Oxford University Press.
Kepner, Jeremy; Gilbert, John (2011). Graph Algorithms in The Language of Linear Algebra. Philadelphia, Pennsylvania: SIAM. ISBN 978-0-898719-90-1.

외부 링크

"Graph theory", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
그래프 이론 튜토리얼
연결된 작은 그래프의 검색 가능한 데이터베이스
이미지 갤러리: Wayback Machine 그래프 (2006년 2월 6일 아카이브 완료)
연구자를 위한 간결하고 주석이 달린 그래프 이론 리소스 목록
rocs : 그래프 이론 IDE
라우터의 사회생활 - 사람과 컴퓨터의 그래프에 대해 논하는 비기술 문서
그래프 이론 소프트웨어 - 그래프 이론을 가르치고 학습하기 위한 도구
그래프 이론에 대한 라이브러리 및 기타 라이브러리의 온라인 서적 및 라이브러리 리소스
그래프 라이브러리 구현에 대한 참조 및 링크가 포함된 그래프 알고리즘 목록

온라인 교재

조합적 최적화 문제에서의 위상변화, 섹션 3: 하르트만과 바이그의 그래프 소개 (2006)
디그래프: Jorgen Bang-Jensen과 Gregory Gutin의 이론 알고리즘과 응용 프로그램 2007
Rinehard Diestel의 그래프 이론

[FOOTNOTEBenderWilliamson2010148-1] 벤더 & 윌리엄슨 2010, 페이지 148

[2] 예를 들어, 이야나가와 카와다 69 J 페이지 234 또는 빅스 페이지 4를 보십시오.

[FOOTNOTEBenderWilliamson2010149-3] 벤더 & 윌리엄슨 2010, 페이지 149

[4] 예를 들면, Graham 등, 페이지 5를 참조해 주세요.

[FOOTNOTEBenderWilliamson2010161-5] 벤더 & 윌리엄슨 2010, 페이지 161. 161

[6] Hale, Scott A. (2013). "Multilinguals and Wikipedia Editing". Proceedings of the 2014 ACM Conference on Web Science - WebSci '14: 99–108. arXiv:1312.0976. Bibcode:2013arXiv1312.0976H. doi:10.1145/2615569.2615684. ISBN 9781450326223. S2CID 14027025.

[7] Mashaghi, A.; et al. (2004). "Investigation of a protein complex network". European Physical Journal B. 41 (1): 113–121. arXiv:cond-mat/0304207. Bibcode:2004EPJB...41..113M. doi:10.1140/epjb/e2004-00301-0. S2CID 9233932.

[8] Shah, Preya; Ashourvan, Arian; Mikhail, Fadi; Pines, Adam; Kini, Lohith; Oechsel, Kelly; Das, Sandhitsu R; Stein, Joel M; Shinohara, Russell T (2019-07-01). "Characterizing the role of the structural connectome in seizure dynamics". Brain. 142 (7): 1955–1972. doi:10.1093/brain/awz125. ISSN 0006-8950. PMC 6598625. PMID 31099821.

[9] Adali, Tulay; Ortega, Antonio (May 2018). "Applications of Graph Theory [Scanning the Issue]". Proceedings of the IEEE. 106 (5): 784–786. doi:10.1109/JPROC.2018.2820300. ISSN 0018-9219.

[10] Grandjean, Martin (2016). "A social network analysis of Twitter: Mapping the digital humanities community" (PDF). Cogent Arts & Humanities. 3 (1): 1171458. doi:10.1080/23311983.2016.1171458. S2CID 114999767.

[11] Vecchio, F (2017). ""Small World" architecture in brain connectivity and hippocampal volume in Alzheimer's disease: a study via graph theory from EEG data". Brain Imaging and Behavior. 11 (2): 473–485. doi:10.1007/s11682-016-9528-3. PMID 26960946. S2CID 3987492.

[12] Vecchio, F (2013). "Brain network connectivity assessed using graph theory in frontotemporal dementia". Neurology. 81 (2): 134–143. doi:10.1212/WNL.0b013e31829a33f8. PMID 23719145. S2CID 28334693.

[13] Bjorken, J. D.; Drell, S. D. (1965). Relativistic Quantum Fields. New York: McGraw-Hill. p. viii.

[14] Kumar, Ankush; Kulkarni, G. U. (2016-01-04). "Evaluating conducting network based transparent electrodes from geometrical considerations". Journal of Applied Physics. 119 (1): 015102. Bibcode:2016JAP...119a5102K. doi:10.1063/1.4939280. ISSN 0021-8979.

[15] Newman, Mark (2010). Networks: An Introduction (PDF). Oxford University Press. Archived from the original (PDF) on 2020-07-28. Retrieved 2019-10-30.

[16] 그랜드장, 마틴(2015).소셜 네트워크 분석 및 시각화: 모레노의 소시오그래픽이 다시 찾아왔다.Moreno(1934년), Who Shall Survive를 기반으로 네트워크를 재설계.

[17] Rosen, Kenneth H. (2011-06-14). Discrete mathematics and its applications (7th ed.). New York: McGraw-Hill. ISBN 978-0-07-338309-5.

[18] Kelly, S.; Black, Michael (2020-07-09). "graphsim: An R package for simulating gene expression data from graph structures of biological pathways". Journal of Open Source Software. The Open Journal. 5 (51): 2161. Bibcode:2020JOSS....5.2161K. bioRxiv 10.1101/2020.03.02.972471. doi:10.21105/joss.02161. ISSN 2475-9066. S2CID 214722561.

[19] Shah, Preya; Ashourvan, Arian; Mikhail, Fadi; Pines, Adam; Kini, Lohith; Oechsel, Kelly; Das, Sandhitsu R; Stein, Joel M; Shinohara, Russell T (2019-07-01). "Characterizing the role of the structural connectome in seizure dynamics". Brain. 142 (7): 1955–1972. doi:10.1093/brain/awz125. ISSN 0006-8950. PMC 6598625. PMID 31099821.

[Biggs-20] Biggs, N.; Lloyd, E.; Wilson, R. (1986), Graph Theory, 1736-1936, Oxford University Press

[Cauchy-21] Cauchy, A. L. (1813), "Recherche sur les polyèdres - premier mémoire", Journal de l'École Polytechnique, 9 (Cahier 16): 66–86.

[Lhuillier-22] L'Huillier, S.-A.-J. (1812–1813), "Mémoire sur la polyèdrométrie", Annales de Mathématiques, 3: 169–189.

[23] Cayley, A. (1857), "On the theory of the analytical forms called trees", Philosophical Magazine, Series IV, 13 (85): 172–176, doi:10.1017/CBO9780511703690.046, ISBN 9780511703690

[Cayley1-24] Cayley, A. (1875), "Ueber die Analytischen Figuren, welche in der Mathematik Bäume genannt werden und ihre Anwendung auf die Theorie chemischer Verbindungen", Berichte der Deutschen Chemischen Gesellschaft, 8 (2): 1056–1059, doi:10.1002/cber.18750080252.

[Sylvester-25] Sylvester, James Joseph (1878). "Chemistry and Algebra". Nature. 17 (432): 284. Bibcode:1878Natur..17..284S. doi:10.1038/017284a0.

[26] Tutte, W.T. (2001), Graph Theory, Cambridge University Press, p. 30, ISBN 978-0-521-79489-3, retrieved 2016-03-14

[27] Gardner, Martin (1992), Fractal Music, Hypercards, and more…Mathematical Recreations from Scientific American, W. H. Freeman and Company, p. 203

[28] Society for Industrial and Applied Mathematics (2002), "The George Polya Prize", Looking Back, Looking Ahead: A SIAM History (PDF), p. 26, archived from the original (PDF) on 2016-03-05, retrieved 2016-03-14

[29] Heinrich Heesch: Untersuchungen zum Vierfarben 문제.만하임: 1969년 서지학 연구소.

[AA1-30] Appel, K.; Haken, W. (1977), "Every planar map is four colorable. Part I. Discharging", Illinois J. Math., 21 (3): 429–490, doi:10.1215/ijm/1256049011.

[AA2-31] Appel, K.; Haken, W. (1977), "Every planar map is four colorable. Part II. Reducibility", Illinois J. Math., 21 (3): 491–567, doi:10.1215/ijm/1256049012.

[RSST-32] Robertson, N.; Sanders, D.; Seymour, P.; Thomas, R. (1997), "The four color theorem", Journal of Combinatorial Theory, Series B, 70: 2–44, doi:10.1006/jctb.1997.1750.

[33] Kepner, Jeremy; Gilbert, John (2011). Graph Algorithms in the Language of Linear Algebra. SIAM. p. 1171458. ISBN 978-0-898719-90-1.

[1]

[2]

[3]

[4]

[5]

[6]

[9]

[7]

[8]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[22]

[21]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

v t 수학
역사 타임라인 개요 리스트 용어집
기초	범주론 정보 이론 수리논리 수학 철학 집합론 유형 이론
대수학	추상적인 가환성 초등 군론 선형 멀티라인 유니버설 호몰로지
분석.	미적분학. 실제 분석 복잡한 분석 초복잡한 분석 미분 방정식 기능 분석 고조파 분석 측정 이론
디스크리트	조합 그래프 이론 순서론
기하학.	대수적 분석 산술 차동 디스크리트 유클리드 유한
수론	산술 대수적 수론 해석수 이론 디오판토스 기하학
토폴로지	일반 대수적 차동 기하학 호모토피 이론
응용의	공학 수학 수리생물학 수리 화학 수리 경제학 수리금융 수리 물리학 수리심리학 수리사회학 수리통계학 확률 통계 정보 시스템 사이언스 제어 이론 게임 이론 운용 조사
계산	컴퓨터 공학 계산 이론 계산 복잡도 이론 수치 분석 최적화 컴퓨터 대수학
관련 토픽	비공식 수학 레크리에이션 수학 수학과 미술 수학 교육
수학 포털 카테고리 공통 위키프로젝트

v t 컴퓨터 공학
주의: 이 템플릿은 대략 2012 ACM Computing Classification System에 준거하고 있습니다.
하드웨어	프린트 기판 주변기기 집적회로 대규모 통합 시스템온칩(SoC) 소비전력(친환경 컴퓨팅) 전자 설계 자동화 하드웨어 액셀러레이션
컴퓨터 시스템 구성	컴퓨터 아키텍처 임베디드 시스템 실시간 컴퓨팅 신뢰성
네트워크	네트워크 아키텍처 네트워크 프로토콜 네트워크 컴포넌트 네트워크 스케줄러 네트워크 퍼포먼스 평가 네트워크 서비스
소프트웨어 구성	통역사 미들웨어 가상 머신 운영 체제 소프트웨어 품질
소프트웨어 표기법 및 도구	프로그래밍 패러다임 프로그래밍 언어 컴파일러 도메인 고유의 언어 모델링 언어 소프트웨어 프레임워크 통합 개발 환경 소프트웨어 구성 관리 소프트웨어 라이브러리 소프트웨어 저장소
소프트웨어 개발	제어 변수 소프트웨어 개발 프로세스 요건 분석 소프트웨어 설계 소프트웨어 구축 소프트웨어 도입 소프트웨어 엔지니어링 소프트웨어 유지보수 프로그래밍팀 오픈 소스 모델
계산 이론	계산 모형 격식어 오토마타 이론 계산가능성 이론 계산 복잡도 이론 논리 의미론
알고리즘	알고리즘 설계 알고리즘 분석 알고리즘 효율 랜덤화 알고리즘 계산기하학
컴퓨팅의 수학	이산 수학 확률 통계 정보 수학 소프트웨어 정보 이론 수학적 해석 수치 분석 이론 컴퓨터 공학
정보 시스템	데이터베이스 관리 시스템 정보 스토리지 시스템 엔터프라이즈 정보 시스템 소셜 정보 시스템 지리정보시스템 의사결정지원시스템 공정관리시스템 멀티미디어 정보 시스템 데이터 마이닝 디지털 라이브러리 컴퓨팅 플랫폼 디지털 마케팅 월드 와이드 웹 정보 검색
보안.	암호화 형식적인 방법 보안 서비스 침입 탐지 시스템 하드웨어 보안 네트워크 보안 정보 보안 응용 프로그램 보안
인간과 컴퓨터의 상호 작용	상호작용 설계 소셜 컴퓨팅 유비쿼터스 컴퓨팅 시각화 접근성
동시성	동시 컴퓨팅 병렬 컴퓨팅 분산 컴퓨팅 멀티스레딩 멀티프로세서
인공지능	자연어 처리 지식 표현 및 추론 컴퓨터 비전 계획 및 스케줄링 자동화 검색 방법론 제어방법 인공지능의 철학 분산형 인공지능
기계 학습	지도 학습 비지도 학습 강화 학습 멀티태스킹 학습 교차 검증
그래픽스	애니매이션 렌더링 이미지 조작 그래픽스 처리 장치 혼합현실 가상현실 이미지 압축 솔리드 모델링
응용 컴퓨팅	전자상거래 엔터프라이즈 소프트웨어 계산 수학 계산물리학 계산화학 계산생물학 계산사회과학 계산공학 컴퓨터 헬스케어 디지털 아트 전자 출판 사이버 전쟁 전자투표 비디오 게임 워드프로세서 운용 조사 교육용 테크놀로지 문서 관리
카테고리 개요 위키프로젝트 공통

v t 그래프 분석 소프트웨어
공짜	세포 테이프 그래피즈 게피 iGraph 네트워크 X 튤립.
독자 사양	메이플 매스매티카

Search