Graph (discrete mathematics)

A graph with six vertices and seven edges

이산 수학(discrete mathematics), 보다 구체적으로 그래프 이론(graph theory)에서, 그래프(graph)는 대상의 일부 쌍이 어떤 의미에서 "관련된" 대상의 집합(set)에 해당하는 구조입니다. 대상은 꼭짓점(vertices, 노드 또는 점이라고도 함)이라고 불리는 수학적 추상화에 해당하고 관련된 각 꼭짓점의 쌍은 가장자리(edge, 연결 또는 선이라고도 함)라고 불립니다.^[1] 전형적으로, 그래프는 꼭짓점에 대한 점 또는 원의 집합으로 다이어그램 형식(diagrammatic form)으로 표시되며, 가장자리에 대한 직선 또는 곡선으로 연결됩니다. 그래프는 이산 수학(discrete mathematics)에서 연구의 대상 중 하나입니다.

가장자리는 방향화되거나 비-방향화될 수 있습니다. 예를 들어, 만약 꼭짓점이 파티에 있는 사람을 나타내고, 두 사람이 악수를 하면 그들 사이에 가장자리가 있으면, B가 A와 악수를 해야 하는 경우에만 임의의 사람 A가 B와 악수할 수 있기 때문에 이 그래프는 비-방향화된 것입니다. 반대로, 사람 A에서 사람 B로의 가장자리가 A가 B에게 돈을 빚지고 있다는 것을 의미하면, 돈을 빚진 것이 반드시 교환되는 것은 아니기 때문에 이 그래프는 방향화된 것입니다.

그래프는 그래프 이론에 의해 공부하는 기본 주제입니다. "그래프"라는 단어는 1878년 J. J. Sylvester에 의해 수학과 화학 구조 (그가 화학-그래픽 이미지라고 부른 것) 사이의 직접적인 관계 때문에 이러한 의미로 처음 사용되었습니다.^[2]^[3]

Definitions

그래프 이론에서 정의는 다양합니다. 다음은 그래프 및 관련 수학적 구조(mathematical structures)를 정의하는 보다 기본적인 방법 중 일부입니다.

Graph

그래프 (때때로 방향화된 그래프와 그것을 구별하기 위해 비-방향화된 그래프, 또는 다중-그래프와 그것을 구별하기 위해 단순 그래프라고 함)는 쌍 $G = (V, E)$ 이며, 여기서 $V$ 는 원소가 꼭짓점이라고 불리는 집합이고, $E$ 는 원소가 가장자리 (때때로 링크 또는 선)이라고 불리는 한 쌍의 꼭짓점의 집합입니다.^[4]^[5]

가장자리 ${x, y}$ 의 꼭짓점 $x$ 와 $y$ 는 가장자리의 끝점이라고 불립니다. 가장자리는 $x$ 와 $y$ 를 연결하고(join) $x$ 와 $y$ 에 입사된다(incident)고 합니다. 꼭짓점은 가장자리에 속하지 않을 수 있고, 이 경우에서 그것은 임의의 다른 꼭짓점에 연결되지 않습니다.

다중-그래프(multigraph)는 여러 가장자리가 같은 끝점의 쌍을 갖도록 허용하는 일반화입니다. 일부 텍스트에서, 다중-그래프는 단순히 그래프라고 불립니다.^[6]^[7]

때때로, 그래프는 꼭짓점을 자신과 연결하는 가장자리인 루프(loops)를 포함할 수 있습니다. 루프를 허용하기 위해, $E$ 에서 꼭짓점의 쌍이 같은 노드를 두 번 가질 수 있어야 합니다. 그러한 일반화된 그래프는 루프를 갖는 그래프(graphs with loops) 또는 루프가 허용되는 문맥에서 명확할 때 단순히 그래프라고 불립니다.

일반적으로, 꼭짓점의 집합 $V$ 는 유한하다고 가정됩니다; 이것은 가장자리의 집합도 유한함을 의미합니다. 무한 그래프(Infinite graphs)는 때때로 고려되지만, 특수한 종류의 이항 관계(binary relation)로 더 자주 보는데, 왜냐하면 유한 그래프에 대한 대부분의 결과가 무한 사례로 확장되지 않거나, 다소 다른 증명이 필요하기 때문입니다.

빈 그래프(empty graph)는 꼭짓점의 빈 집합 (및 따라서 가장자리의 빈 집합)을 가지는 그래프입니다. 그래프의 차수(order)는 꼭짓점의 개수 $| V |$ 입니다. 그래프의 크기는 가장자리의 개수 $| E |$ 입니다. 어쨌든, 알고리듬의 계산 복잡성(computational complexity)을 표현하는 것과 같은 일부 문맥에서, 크기는 $| V | + | E |$ 입니다 (그렇지 않으면, 비-빈 그래프는 크기 0을 가질 수 있습니다.) 꼭짓점의 정도(degree) 또는 결합가(valency)는 꼭짓점에 입사하는 가장자리의 개수입니다; 루프를 갖는 그래프에 대해, 하나의 루프는 두 번 계산됩니다.^[1]

차수 $n$ 의 그래프에서, 각 꼭짓점의 최대 정도는 $n - 1$ (또는 루프가 허용되면 $n + 1$ 인데, 왜냐하면 루프가 정도에 2를 기여하기 때문)이고, 최대 가장자리의 개수는 $n (n - 1)/2$ (또는 루프가 허용되면 $n (n + 1)/2$ )입니다.

그래프의 가장자리는 인접 관계(adjacency relation)라고 불리는 꼭짓점의 대칭 관계(symmetric relation)를 정의합니다. 구체적으로 특히, 두 꼭짓점 $x$ 와 $y$ 는 ${x, y}$ 가 가장자리이면 인접입니다. 그래프는 $n \times n$ 정사각 행렬인 인접 행렬(adjacency matrix) $A$ 에 의해 완전히 지정될 수 있으며, $A ij$ 는 꼭짓점 $i$ 에서 꼭짓점 $j$ 까지의 연결의 개수를 지정합니다. 단순 그래프에 대해, $A ij$ 는 연결 해제를 나타내는 0이거나, 연결을 나타내는 1입니다; 게다가 $A ii = 0$ 인데 왜냐하면 단순 그래프에서 가장자리는 같은 꼭짓점에서 시작하고 끝날 수 없기 때문입니다. 자체-루프를 갖는 그래프는 일부 또는 모든 $A ii$ 가 양의 정수와 같다는 특징이 있고, 다중-그래프 (꼭짓점 사이에 다중 가장자리가 있음)는 일부 또는 모든 $A ij$ 가 양의 정수와 같다는 특징이 있습니다. 비-방향화된 그래프는 대칭 인접 행렬을 가집니다 ( $A ij = A ji$ 를 의미합니다).

Directed graph

방향화된 그래프(directed graph) 또는 다이그래프(digraph)는 가장자리가 방향을 가지는 그래프입니다.

그 용어의 하나의 제한적이지만 매우 공통적인 의미에서,^[8] 방향화된 그래프는 다음을 구성하는 쌍 $G = (V, E)$ 입니다:

$V$ , 꼭짓점의 집합(set) (역시 노드 또는 점이라고 불림);
$E$ , 가장자리의 집합(set) (역시 directed edges, directed links, directed lines, arrows, 또는 arcs라고 불림), 이는 구별되는 꼭짓점의 순서화된 쌍(ordered pairs)입니다: $E\subseteq \{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\}$ .

모호함을 피하기 위해, 이러한 유형의 대상은 정확히 방향화된 단순 그래프(directed simple graph)라고 부를 수 있습니다.

$x$ 에서 $y$ 로 향하는 가장자리 $(x, y)$ 에서, 꼭짓점 $x$ 와 $y$ 는 가장자리의 끝점, $x$ 는 가장자리의 꼬리, $y$ 는 가장자리의 머리라고 불립니다. 가장자리는 $x$ 와 $y$ 를 연결하고 $x$ 와 $y$ 에 입사된다고 말합니다. 꼭짓점은 그래프에 존재할 수 있고 가장자리에 속하지 않을 수 있습니다. 가장자리 $(y, x)$ 는 $(x, y)$ 의 반전된 가장자리라고 불립니다. 위의 정의 아래에서 허용되지 않는 다중 가장자리(Multiple edges)는 같은 꼬리와 같은 머리 둘 다를 갖는 두 개 이상의 가장자리입니다.

다중 가장자리를 허용하는 용어의 또 다른 일반적인 의미에서,^[8] 방향화된 그래프(directed graph)는 다음을 구성하는 순서화된 세-쌍 $G = (V, E, ϕ)$ 입니다:

$V$ , 꼭짓점의 집합(set) (역시 노드 또는 점이라고 불림);
$E$ , 가장자리의 집합(set) (역시 directed edges, directed links, directed lines, arrows 또는 arcs라고 불림);
$ϕ$ , 모든 각 가장자리를 꼭짓점의 순서화된 쌍으로 매핑하는 입사 함수(incidence function) (즉, 가장자리는 두 개의 구별되는 꼭짓점과 결합됩니다): $\phi :E\to \{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\}$ .

모호함을 피하기 위해, 이러한 유형의 대상은 정확히 방향화된 다중-그래프(directed multigraph)라고 불릴 수 있습니다.

루프(loop)는 꼭짓점을 자체와 연결하는 가장자리입니다. 위의 두 가지 정의에 정의된 것처럼 방향화된 그래프는 루프를 가질 수 없는데, 왜냐하면 꼭짓점 $x$ 를 자체에 연결하는 루프가 (방향화된 단순 그래프에 대해) 가장자리이거나 $\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\}$ 에 있지 않은 (방향화된 다중그래프에 대해) $(x,x)$ 에 입사하기 때문입니다. 따라서 루프를 허용하기 위해 정의는 확장되어야 합니다. 방향화된 단순 그래프에 대해, $E$ 의 정의는 $E\subseteq \{(x,y)\mid (x,y)\in V^{2}\}$ 로 수정되어야 합니다. 방향화된 다중그래프에 대해, $\phi$ 의 정의는 $\phi :E\to \{(x,y)\mid (x,y)\in V^{2}\}$ 로 수정되어야 합니다. 모호함을 피하기 위해, 이러한 유형의 대상은 각각 루프를 허용하는 방향화된 단순 그래프(directed simple graph permitting loops)와 루프 (또는 퀴버(quiver))를 허용하는 방향화된 다중그래프라고 불릴 수 있습니다.

루프 $G$ 를 허용하는 방향화된 단순 그래프의 가장자리는 $G$ 의 인접 관계(adjacency relation)라고 불리는 $G$ 의 꼭짓점에 대한 동차 관계(homogeneous relation) ~입니다. 구체적으로, 각 가장자리 $(x, y)$ 에 대해, 그것의 끝점 $x$ 와 $y$ 는 서로 인접된다(adjacent)고 말하며, $x ~ y$ 로 표시됩니다.

Mixed graph

혼합 그래프(mixed graph)는 일부 가장자리가 방향화될 수 있고 일부는 비-방향화될 수 있는 그래프입니다. 그것은 $V$ , $E$ (비-방향화된 가장자리), $A$ (방향화된 가장자리), 위에서 처럼 정의된 $ϕ E$ 와 $ϕ A$ 를 갖는 혼합 단순 그래프에 대해 순서화된 세-쌍 $G = (V, E, A)$ 과 혼합 다중-그래프에 대해 $G = (V, E, A, ϕ E, ϕ A)$ 입니다. 방향화된 그래프와 비-방향화된 그래프는 특수한 경우입니다.

Weighted graph

가중 그래프(weighted graph) 또는 네트워크(network)는 각 가장자리에 숫자 (가중)가 할당된 그래프입니다.^[9]^[10]^[11] 그러한 가중은 당면한 문제에 따라, 예를 들어, 비용, 길이, 또는 용량을 나타낼 수 있습니다. 그러한 그래프는 예를 들어 여행하는 세일즈맨 문제(traveling salesman problem)와 같은 최단 경로 문제(shortest path problems)와 같은 많은 상황에서 발생합니다.

Types of graphs

Oriented graph

방향화된 그래프의 한 가지 정의는 (x, y)와 (y, x) 중 많아야 하나가 그래프의 가장자리일 수 있는 방향화된 그래프라는 것입니다. 즉, 그것은 방향화된 (단순) 그래프의 방향(orientation)으로 형성될 수 있는 방향화된 그래프입니다.

일부 저자는 "oriented graph"를 "directed graph"와 같은 의미로 사용합니다. 일부 저자는 "oriented graph"를 주어진 비-방향화된 그래프 또는 다중-그래프의 임의의 방향을 의미하기 위해 사용합니다.

Regular graph

정규 그래프(regular graph)는 각 꼭짓점이 같은 숫자의 이웃을 가지는, 즉, 모든 각 꼭짓점이 같은 차수를 가지는 그래프입니다. 차수 k의 꼭짓점을 갖는 정규 그래프는 k-정규 그래프 또는 차수 k의 정규 그래프라고 불립니다.

Complete graph

완전 그래프(complete graph)는 꼭짓점의 각 쌍이 가장자리로 연결된 그래프입니다. 완전 그래프는 모든 가능한 가장자리를 포함합니다.

Finite graph

유한 그래프(finite graph)는 꼭짓점 집합과 가장자리 집합이 유한 집합(finite sets)인 그래프입니다. 그렇지 않으면, 그것은 무한 그래프(infinite graph)라고 불립니다.

그래프 이론에서 가장 공통적으로 논의되는 그래프는 유한하다는 것을 암시합니다. 만약 그래프가 무한하면, 그것은 보통 구체적으로 명시됩니다.

Connected graph

비-방향화된 그래프에서, 비-순서화된 꼭짓점의 쌍 {x, y}는 만약 경로가 x에서 y로 이어지면 연결된(connected) 것이라고 불립니다. 그렇지 않으면, 비-순서화된 쌍은 분리된(disconnected) 것이라고 불립니다.

연결된 그래프(connected graph)는 그래프에서 꼭짓점의 모든 각 비-순서화된 쌍이 연결된 비-방향화된 그래프(undirected graph)입니다. 그렇지 않으면, 그것은 분리된 그래프라고 불립니다.

방향화된 그래프에서, 꼭짓점의 순서화된 쌍 (x, y)은 만약 방향화된 경로가 x에서 y로 이어지면 강하게 연결된(strongly connected) 것이라고 불립니다. 그렇지 않으면, 순서화된 쌍은 만약 비-방향화된 경로가 방향화된 가장자리의 모두를 비-방향화된 가장자리로 바꾼 후 x에서 y로 이어지면 약하게 연결된(weakly connected) 것이라고 불립니다. 그렇지 않으면, 순서화된 쌍은 분리된 것이라고 불립니다.

강하게 연결된 그래프(strongly connected graph)는 그래프에서 꼭짓점의 모든 각 순서화된 쌍이 강하게 연결된 방향화된 그래프입니다. 그렇지 않으면, 그것은 만약 그래프에서 꼭짓점의 모든 각 순서화된 쌍이 약하게 연결된 약하게 연결된 그래프(weakly connected graph)라고 불립니다. 그렇지 않으면, 그것은 분리된 그래프(disconnected graph)라고 불립니다.

k-꼭짓점 연결된 그래프 또는 k-가장자리 연결된 그래프는 제거될 때 그래프를 연결 해제하는 k − 1개의 꼭짓점 (각각, 가장자리)의 집합이 존재하지 않는 그래프입니다. k-꼭짓점 연결된 그래프는 종종 단순히 k-연결된 그래프라고 불립니다.

Bipartite graph

이분 그래프(bipartite graph)는 꼭짓점 집합이 W에서 두 꼭짓점이 공통 가장자리를 공유하지 않고 X에서 두 꼭짓점도 공통 가장자리를 공유하지 않도록 두 집합, W와 X로 분할될 수 있는 단순 그래프입니다. 대안적으로, 그것은 2의 색칠 숫자(chromatic number)를 갖는 그래프입니다.

완전 이분 그래프(complete bipartite graph)에서, 꼭짓점 집합은 W에서 모든 각 꼭짓점이 X에서 모든 각 꼭짓점에 인접하지만 W 또는 X 내에 가장자리가 없도록 두 개의 서로소 집합, W와 X의 합집합입니다.

Path graph

차수 n ≥ 2의 경로 그래프(path graph) 또는 선형 그래프(linear graph)는 가장자리가 {v_i, v_i+1}임을 만족하는 꼭짓점이 순서 v₁, v₂, …, v_n에서 나열될 수 있는 그래프이며, 여기서 i = 1, 2, …, n − 1입니다. 경로 그래프는 2개를 제외한 모든 꼭짓점의 차수가 2이고 남아있는 2개의 꼭짓점의 차수가 1인 연결된 그래프로 특징지을 수 있습니다. 만약 경로 그래프가 또 다른 그래프의 부분그래프(subgraph)로 발생하면, 그것은 해당 그래프에서 경로(path)입니다.

Planar graph

평면 그래프(planar graph)는 두 개의 가장자리가 교차하지 않음을 만족하는 꼭짓점과 가장자리가 평면에 그려질 수 있는 그래프입니다.

Cycle graph

차수 n ≥ 3의 순환 그래프(cycle graph) 또는 원형 그래프(circular graph)는 가장자리는 {v_i, v_i+1} + 가장자리 {v_n, v₁}임을 만족하는 꼭짓점이 v₁, v₂, …, v_n 순서로 나열될 수 있는 그래프이며, 여기서 i = 1, 2, …, n − 1입니다. 순환 그래프는 모든 꼭짓점의 차수가 2인 연결된 그래프로 특징지을 수 있습니다. 만약 순환 그래프가 또 다른 그래프의 부분그래프로 나타나면, 그것은 해당 그래프에서 순환(cycle) 또는 회로(circuit)입니다.

Tree

트리(tree)는 임의의 두 꼭짓점이 정확히 하나의 경로로 연결된 비-방향화된 그래프, 또는 동등하게 연결된 비순환 비-방향화된 그래프입니다.

포리스트(forest)는 임의의 두 꼭짓점이 많아야 하나의 경로로 연결된 비-방향화된 그래프, 또는 동등하게 비순환 비-방향화된 그래프, 또는 동등하게 트리의 서로소 합집합(disjoint union)입니다.

Polytree

폴리트리(polytree, 또는 방향화된 트리(directed tree 또는 oriented tree) 또는 단일 연결된 네트워크(singly connected network))는 놓여있는 비-방향화된 그래프가 트리인 방향화된 비순환 그래프(directed acyclic graph, DAG)입니다.

폴리포레스트(polyforest, 또는 방향화된 포리스트(directed forest 또는 oriented forest))는 놓여있는 비-방향화된 그래프가 포리스트인 방향화된 비순환 그래프입니다.

Advanced classes

보다 고급 그래프 종류는 다음과 같습니다:

페테르센 그래프(Petersen graph)와 그것의 일반화;
완전 그래프(perfect graphs);
cographs;
chordal graphs;
other graphs with large automorphism groups: vertex-transitive, arc-transitive, and distance-transitive graphs;
strongly regular graphs and their generalizations distance-regular graphs.

Properties of graphs

그래프의 두 가장자리가 공통 꼭짓점을 공유하면 인접(adjacent)이라고 불립니다. 방향화된 그래프의 두 가장자리는 첫 번째 가장자리의 머리가 두 번째 가장자리의 꼬리이면 연속적(consecutive)이라고 불립니다. 유사하게, 두 꼭짓점이 공통 가장자리를 공유하면 인접 (첫 번째 꼭짓점이 꼬리이고 두 번째 꼭짓점이 가장자리의 머리이면 연속적)이라고 불리며, 이 경우에서 공통 가장자리는 두 꼭짓점을 결합한다(join)고 말합니다. 가장자리와 해당 가장자리의 꼭짓점은 입사(incident)라고 불립니다.

오직 하나의 꼭짓점을 갖고 가장자리가 없는 그래프는 자명한 그래프(trivial graph)라고 불립니다. 꼭짓점만 있고 가장자리가 없는 그래프는 가장자리-없는 그래프(edgeless graph)로 알려져 있습니다. 꼭짓점도 없고 가장자리도 없는 그래프는 때때로 널 그래프(null graph) 또는 빈 그래프(empty graph)라고 불리지만, 그 용어는 일관적이지 않고 모든 수학자들이 이 대상을 허용하는 것은 아닙니다.

통상적으로, 그래프의 꼭짓점은, 집합의 원소로서의 본성에 따라, 구별-가능입니다. 이러한 종류의 그래프는 꼭짓점-레이블된(vertex-labeled) 것이라고 불릴 수 있습니다. 어쨌든, 많은 질문에 대해 꼭짓점을 비-구별가능으로 취급하는 것이 좋습니다. (물론, 꼭짓점은 그래프 자체의 속성, 예를 들어, 입사 가장자리의 개수로 여전히 구별-가능일 수 있습니다.) 같은 설명이 가장자리에 적용되므로, 레이블된 가장자리를 갖는 그래프는 가장자리-레이블된(edge-labeled) 것이라고 불립니다. 꼭짓점 또는 가장자리에 부착된 레이블을 갖는 그래프는 일반적으로 레이블된(labeled) 것으로 퇴화됩니다. 결과적으로, 꼭짓점이 구-구별가능이고 가장자리가 비-구별가능인 그래프는 비-레이블된 것이라고 불립니다. (문헌에서, 레이블된( labeled)이라는 용어는 서로 다른 꼭짓점이나 가장자리를 구별하기 위해서만 역할을 하는 것 외에 다른 종류의 레이블링에도 적용될 수 있습니다.)

모든 그래프의 카테고리(category)는 쉼표 카테고리(comma category) Set ↓ D이며, 여기서 D: Set → Set는 집합 s를 s × s로 취하는 함수자(functor)입니다.

Examples

다이어그램은 꼭짓점 $V=\{1,2,3,4,5,6\}$ 과 가장자리 $E=\{\{1,2\},\{1,5\},\{2,3\},\{2,5\},\{3,4\},\{4,5\},\{4,6\}\}$ 를 갖는 그래프의 도식적 표현입니다.
컴퓨터 과학(computer science)에서, 방향화된 그래프는 지식 (예를 들어, 개념 그래프), 유한 상태 기계, 및 기타 많은 이산 구조를 나타내기 위해 사용됩니다.
집합 X 위에 이항 관계(binary relation) R은 방향화된 그래프를 정의합니다. X의 원소 x는 X에서 원소 y의 직접 전임자인 것과 xRy인 것은 필요충분 조건입니다.
방향화된 그래프는 한 사용자가 또 다른 사용자를 팔로우하는 Twitter와 같은 정보 네트워크를 모델링할 수 있습니다.^[12]^[13]
방향화된 그래프의 특히 규칙적인 예제는 유한하게-생성된 그룹의 케일리 그래프(Cayley graph)와 슈라이어 코셋 그래프(Schreier coset graphs)에 의해 제공됩니다.
카테고리 이론(category theory)에서, 모든 각 작은 카테고리(small category)는 꼭짓점이 카테고리의 대상이고 가장자리가 카테고리의 화살표인 놓여있는 방향화된 다중-그래프를 가집니다. 카테고리 이론의 언어에서, 작은 카테고리의 카테고리에서 화살통의 카테고리(category of quivers)로 가는 망각 함수자(forgetful functor)가 있다고 말합니다.

Graph operations

다음 카테고리로 분류될 수 있는 초기 그래프에서 새로운 그래프를 생성하는 몇 가지 연산이 있습니다:

단항 연산(unary operations), 이는 다음과 같은 초기 그래프에서 새로운 그래프를 생성합니다:
- edge contraction,
- line graph,
- dual graph,
- complement graph,
- graph rewriting;
이항 연산(binary operations), 이는 다음과 같은 두 개의 초기 그래프에서 새로운 그래프를 생성합니다:

Generalizations

초-그래프(hypergraph)에서, 가장자리는 세 개 이상의 꼭짓점을 결합할 수 있습니다.

비-방향화된 그래프는 1-심플렉스 (가장자리)와 0-심플렉스 (꼭짓점)로 구성된 단순 복합체(simplicial complex)로 볼 수 있습니다. 이를테면, 복합체는 고-차원 심플레스를 허용하므로 그래프의 일반화입니다.

모든 각 그래프는 매트로이드(matroid)를 발생시킵니다.

모델 이론(model theory)에서, 그래프는 구조(structure)일뿐입니다. 그러나 해당 경우에서, 가장자리의 숫자에는 제한이 없습니다: 그것은 임의의 세는 숫자(cardinal number)일 수 있으며, 연속 그래프(continuous graph)를 참조하십시오.

계산 생물학(computational biology)에서, 파워 그래프 분석(power graph analysis)은 비-방향화된 그래프의 대안적인 표현으로 파워 그래프를 도입합니다.

지리 정보 시스템(geographic information systems)에서, 기하학적 네트워크(geometric networks)는 그래프를 밀접하게 모델링하고, 그래프 이론에서 많은 개념을 차용하여 도로 네트워크 또는 유틸리티 그리드에 대한 공간 분석을 수행합니다.

Notes

^ ^a ^b Trudeau, Richard J. (1993). Introduction to Graph Theory (Corrected, enlarged republication. ed.). New York: Dover Pub. p. 19. ISBN 978-0-486-67870-2. Archived from the original on 5 May 2019. Retrieved 8 August 2012. A graph is an object consisting of two sets called its vertex set and its edge set.
^
See:
- J. J. Sylvester (February 7, 1878) "Chemistry and algebra," Archived 2023-02-04 at the Wayback Machine Nature, 17 : 284. doi:10.1038/017284a0. From page 284: "Every invariant and covariant thus becomes expressible by a graph precisely identical with a Kekuléan diagram or chemicograph."
- J. J. Sylvester (1878) "On an application of the new atomic theory to the graphical representation of the invariants and covariants of binary quantics, – with three appendices," Archived 2023-02-04 at the Wayback Machine American Journal of Mathematics, Pure and Applied, 1 (1) : 64–90. doi:10.2307/2369436. JSTOR 2369436. The term "graph" first appears in this paper on page 65.
^ Gross, Jonathan L.; Yellen, Jay (2004). Handbook of graph theory. CRC Press. p. 35. ISBN 978-1-58488-090-5. Archived from the original on 2023-02-04. Retrieved 2016-02-16.
^ Bender & Williamson 2010, p. 148.
^ See, for instance, Iyanaga and Kawada, 69 J, p. 234 or Biggs, p. 4.
^ Bender & Williamson 2010, p. 149.
^ Graham et al., p. 5.
^ ^a ^b Bender & Williamson 2010, p. 161.
^ Strang, Gilbert (2005), Linear Algebra and Its Applications (4th ed.), Brooks Cole, ISBN 978-0-03-010567-8
^ Lewis, John (2013), Java Software Structures (4th ed.), Pearson, p. 405, ISBN 978-0133250121
^ Fletcher, Peter; Hoyle, Hughes; Patty, C. Wayne (1991). Foundations of Discrete Mathematics (International student ed.). Boston: PWS-KENT Pub. Co. p. 463. ISBN 978-0-53492-373-0. A weighted graph is a graph in which a number w(e), called its weight, is assigned to each edge e.
^ Grandjean, Martin (2016). "A social network analysis of Twitter: Mapping the digital humanities community". Cogent Arts & Humanities. 3 (1): 1171458. doi:10.1080/23311983.2016.1171458. Archived from the original on 2021-03-02. Retrieved 2019-09-16.
^ Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang, and Reza Bosagh Zadeh WTF: The who-to-follow system at Twitter Archived 2019-07-12 at the Wayback Machine, Proceedings of the 22nd international conference on World Wide Web. doi:10.1145/2488388.2488433.

References

Balakrishnan, V. K. (1997). Graph Theory (1st ed.). McGraw-Hill. ISBN 978-0-07-005489-9.
Bang-Jensen, J.; Gutin, G. (2000). Digraphs: Theory, Algorithms and Applications. Springer.
Bender, Edward A.; Williamson, S. Gill (2010). Lists, Decisions and Graphs. With an Introduction to Probability.
Berge, Claude (1958). Théorie des graphes et ses applications (in French). Paris: Dunod.
Biggs, Norman (1993). Algebraic Graph Theory (2nd ed.). Cambridge University Press. ISBN 978-0-521-45897-9.
Bollobás, Béla (2002). Modern Graph Theory (1st ed.). Springer. ISBN 978-0-387-98488-9.
Diestel, Reinhard (2005). Graph Theory (3rd ed.). Berlin, New York: Springer-Verlag. ISBN 978-3-540-26183-4.
Graham, R.L.; Grötschel, M.; Lovász, L. (1995). Handbook of Combinatorics. MIT Press. ISBN 978-0-262-07169-7.
Gross, Jonathan L.; Yellen, Jay (1998). Graph Theory and Its Applications. CRC Press. ISBN 978-0-8493-3982-0.
Gross, Jonathan L.; Yellen, Jay (2003). Handbook of Graph Theory. CRC. ISBN 978-1-58488-090-5.
Harary, Frank (1995). Graph Theory. Addison Wesley Publishing Company. ISBN 978-0-201-41033-4.
Iyanaga, Shôkichi; Kawada, Yukiyosi (1977). Encyclopedic Dictionary of Mathematics. MIT Press. ISBN 978-0-262-09016-2.
Zwillinger, Daniel (2002). CRC Standard Mathematical Tables and Formulae (31st ed.). Chapman & Hall/CRC. ISBN 978-1-58488-291-6.

External links

Media related to Graph (discrete mathematics) at Wikimedia Commons
Weisstein, Eric W. "Graph". MathWorld.

[:0-1] Trudeau, Richard J. (1993). Introduction to Graph Theory (Corrected, enlarged republication. ed.). New York: Dover Pub. p. 19. ISBN 978-0-486-67870-2. Archived from the original on 5 May 2019. Retrieved 8 August 2012. A graph is an object consisting of two sets called its vertex set and its edge set.

[2] See:
J. J. Sylvester (February 7, 1878) "Chemistry and algebra," Archived 2023-02-04 at the Wayback Machine Nature, 17 : 284. doi:10.1038/017284a0. From page 284: "Every invariant and covariant thus becomes expressible by a graph precisely identical with a Kekuléan diagram or chemicograph."

J. J. Sylvester (1878) "On an application of the new atomic theory to the graphical representation of the invariants and covariants of binary quantics, – with three appendices," Archived 2023-02-04 at the Wayback Machine American Journal of Mathematics, Pure and Applied, 1 (1) : 64–90. doi:10.2307/2369436. JSTOR 2369436. The term "graph" first appears in this paper on page 65.

[3] J. J. Sylvester (February 7, 1878) "Chemistry and algebra," Archived 2023-02-04 at the Wayback Machine Nature, 17 : 284. doi:10.1038/017284a0. From page 284: "Every invariant and covariant thus becomes expressible by a graph precisely identical with a Kekuléan diagram or chemicograph."

[4] J. J. Sylvester (1878) "On an application of the new atomic theory to the graphical representation of the invariants and covariants of binary quantics, – with three appendices," Archived 2023-02-04 at the Wayback Machine American Journal of Mathematics, Pure and Applied, 1 (1) : 64–90. doi:10.2307/2369436. JSTOR 2369436. The term "graph" first appears in this paper on page 65.

[3] Gross, Jonathan L.; Yellen, Jay (2004). Handbook of graph theory. CRC Press. p. 35. ISBN 978-1-58488-090-5. Archived from the original on 2023-02-04. Retrieved 2016-02-16.

[FOOTNOTEBenderWilliamson2010148-4] Bender & Williamson 2010, p. 148.

[5] See, for instance, Iyanaga and Kawada, 69 J, p. 234 or Biggs, p. 4.

[FOOTNOTEBenderWilliamson2010149-6] Bender & Williamson 2010, p. 149.

[7] Graham et al., p. 5.

[FOOTNOTEBenderWilliamson2010161-8] Bender & Williamson 2010, p. 161.

[9] Strang, Gilbert (2005), Linear Algebra and Its Applications (4th ed.), Brooks Cole, ISBN 978-0-03-010567-8

[10] Lewis, John (2013), Java Software Structures (4th ed.), Pearson, p. 405, ISBN 978-0133250121

[11] Fletcher, Peter; Hoyle, Hughes; Patty, C. Wayne (1991). Foundations of Discrete Mathematics (International student ed.). Boston: PWS-KENT Pub. Co. p. 463. ISBN 978-0-53492-373-0. A weighted graph is a graph in which a number w(e), called its weight, is assigned to each edge e.

[snatwitter-12] Grandjean, Martin (2016). "A social network analysis of Twitter: Mapping the digital humanities community". Cogent Arts & Humanities. 3 (1): 1171458. doi:10.1080/23311983.2016.1171458. Archived from the original on 2021-03-02. Retrieved 2019-09-16.

[twitterwtf-13] Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang, and Reza Bosagh Zadeh WTF: The who-to-follow system at Twitter Archived 2019-07-12 at the Wayback Machine, Proceedings of the 22nd international conference on World Wide Web. doi:10.1145/2488388.2488433.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]