그래프 이론 용어집

이것은 그래프 이론의 용어집이다. 그래프 이론은 그래프, 선이나 가장자리로 쌍으로 연결된 노드 또는 정점 시스템을 연구하는 학문이다.

기호

Square brackets [ ]: $G [S]$ 는 정점 부분 집합 $S$ 에 대한 그래프 $G$ 의 유도 하위 그래프다.
Prime symbol ': 프라임 기호는 주어진 그래프 대신 선 그래프에 적용되도록 그래프 불변성의 표기법을 수정하는 데 종종 사용된다. 예를 들어, $α (G)$ 는 그래프의 독립성 번호, $αα (G)$ 는 그래프의 일치된 번호로, 선 그래프의 독립성 번호와 동일하다. 마찬가지로 $χ (G)$ 는 그래프의 색수, $χ (G)$ 는 그래프의 색지수로서, 선 그래프의 색수(Chromatic number)와 같다.

A

absorbing: 방향 그래프 $G$ $G$ 의 $a$ $흡수$ 집합 A $A$ 은 $g$ 정점 $v\in G\setminus A$ 으로, 모든 정점 v $v\in G\setminus A$ $v\in G\setminus A$ $v\in G\setminus A$ $v\in G\setminus A$ $v\in G\setminus A$ 에 대해 $v\in G\setminus A$ $v$ ${\displaystyle v$ $}$ 에서 A $}$ 의 정점을 향해 $v$ 에지가 있다 $A$
achromatic: 그래프의 무채색 수는 완전한 색상의 최대 색상 수입니다.^[1]
acyclic: 1. 그래프는 주기가 없으면 순환한다. 비방향의 순환 그래프는 숲과 같은 것이다. 지시된 반복 그래프는 종종 반복 지시 그래프라고 불리지 않는다.^[2]; 2. 방향하지 않은 그래프의 반복적인 색상은 두 색 등급마다 숲을 유도하는 적절한 색이다.^[3]
adjacency matrix: 그래프의 인접 행렬은 행과 열이 모두 그래프의 정점에 의해 인덱싱되는 행렬로, $정점$ $i$ 와 j가 인접한 경우 행 $i$ 와 $열$ j에 대한 셀에 1이 있고, 그렇지 않으면 0이 된다.^[4]
adjacent: 1. 같은 에지의 양쪽 끝점인 두 꼭지점 사이의 관계.^[2]; 2. 끝 정점을 공유하는 두 개의 뚜렷한 가장자리 사이의 관계.^[5]
α: 그래프 $G$ 의 경우, $α (G)$ 는 (그리스 문자 알파 사용) 독립성 번호(독립성 참조)이고 $,$ α)( $G)$ 는 일치하는 번호(일치 참조)이다.
alternating: 일치하는 그래프에서 교대 경로는 가장자리가 일치된 가장자리와 일치하지 않는 가장자리 사이를 교대하는 경로다. 교대 사이클은 유사하게 에지가 일치하는 에지와 일치하지 않는 에지 사이를 교대하는 사이클이다. 증강 경로는 불포화 정점에서 시작하고 끝나는 교대 경로다. 일치 경로와 증가 경로의 대칭적 차이로 더 큰 일치를 찾을 수 있다. 일치된 일치는 증가 경로가 없는 경우에만 최대값이다.
antichain: 지시된 Acyclic 그래프에서 쌍으로 비교할 수 없는 정점의 부분 집합 $S$ , 즉 $S$ 의 어떤 $x\leq y$ $x\leq y$ $x\leq y$ $x\leq y$ ${\displaystyle x\leq$ y $}$ 에 대해 $x$ 에서 $y$ 로 또는 $y$ 에서 $x$ 로 향하는 경로가 없다. 부분적으로 정렬된 세트의 항균제 개념에서 영감을 얻었다.
anti-edge: 비에지, 비인접 정점의 쌍과 동의어.
anti-triangle: 삼각형의 보어인 3Vex 독립형 세트.
apex: 1. 꼭지점 그래프는 평면 하위 그래프를 남겨두고 하나의 꼭지점을 제거할 수 있는 그래프를 말한다. 제거된 정점을 정점이라고 한다. k-에이펙스 그래프는 $k$ 정점을 제거하여 평면도를 만들 수 있는 그래프다.; 2. 다른 모든 정점에 인접한 정점인 보편 정점의 동의어.
arborescence: 루트 및 방향 트리의 동의어. 트리를 참조하십시오.
arc: 가장자리를 보다.
arrow: 지시된 그래프의 가장자리 등 순서가 지정된 꼭지점 쌍. 화살표 $(x,$ $y)$ 는 꼬리 $x$ , $머리$ y, $그리고$ $x$ 에서 y까지의 방향을 가지고 있다. $y$ 는 $x$ 와 $x$ 의 직접적인 전신인 $y$ 의 직접적인 계승자라고 한다. 화살표 $(y,$ $x)$ 는 화살표 $(x,$ y)의 반전 화살표다 $.$
articulation point: 연결된 그래프에서 제거하면 그래프가 분리되는 꼭지점.
-ary: k-arry 트리는 모든 내부 꼭지점에 $k자녀$ 이상이 없는 뿌리깊은 나무다. 1에이리의 나무는 하나의 길일 뿐이다. 2-ari 트리는 2-ari 트리라고도 불리는데, 그 용어가 더 적절하게 각 노드의 아이들이 (각 타입의 거의 하나와 함께) 왼쪽이나 오른쪽 아이로 구별되는 2-ari 트리를 가리킨다. 모든 내부 꼭지점에 정확히 $k자녀$ 가 있으면 k자녀가 완성된다고 한다.
augmenting: 교대 경로의 특수 유형. 교대 경로를 참조하십시오.
automorphism: 그래프 자동형은 그래프의 대칭이며, 그래프에서 그 자체로 이형성이다.

B

bag: 트리 분해의 정점 집합 중 하나.
balanced: 두 개의 꼭지점 파티션의 각 부분 집합이 서로 크기가 같을 경우 두 개의 그래프가 균형을 이룬다.
bandwidth: 그래프 $G$ 의 대역폭은 $G$ 의 모든 정점 순서에 걸쳐 가장 긴 에지 길이(두 끝점 사이의 순서 단계 수)의 최소값이다. 또한 클라이크 크기를 최소화하기 위해 선택된 $G$ 의 적절한 간격 완성에서 최대 클라이크 크기보다 한 개 적다.
biclique: 전체 초당적 그래프 또는 전체 초당적 하위 그래프의 동의어. 완전함을 참조하십시오.
biconnected: 보통 2-Vertex 연결의 동의어지만, 2-연결은 아니지만 K를₂ 포함하기도 한다. 연결됨을 참조하고, 연결된 구성 요소에 대해서는 구성 요소를 참조하십시오.
binding number: 정점 부분 집합의 적절한 부분 집합에서 부분 집합의 크기에 대한 가능한 최소 비율.^[6]
bipartite: 쌍방향 그래프는 한 세트의 정점이 서로 연결되지 않고 다른 세트의 정점에 연결될 수 있도록 정점을 두 개의 분리 집합으로 나눌 수 있는 그래프다. 다른 방법으로 말하면, 초당적 그래프는 홀수 주기가 없는 그래프다. 동등하게, 두 가지 색상으로 적절하게 색칠될 수 있는 그래프다. 초당적 그래프는 종종 $G =$ ( $U, V, E)$ 라고 쓰여지는데 $여기$ 서 U와 $V$ 는 각 색상의 정점의 부분 집합이다. 그러나 그래프를 연결하지 않는 한 고유한 2-색상이 없을 수도 있다.
biregular: 이등분 그래프는 정점 분할의 각 집합에 대해 각각 하나씩 두 개의 정점 도만 있는 초당적 그래프다.
block: 1. 그래프 $G$ 의 블럭은 절연 정점, 교량 가장자리 또는 2개의 연결 서브그래프인 최대 서브그래프다. 블록이 2개 연결된 경우, 블록의 모든 꼭지점 쌍은 공통 주기에 속한다. 그래프의 모든 가장자리는 정확히 하나의 블럭에 속한다.; 2. 그래프 $G$ 의 블록 그래프는 $G$ 의 블록인 또 다른 그래프로, 해당 블록이 굴절점을 공유할 때 두 개의 정점을 연결하는 가장자리가 있다. 즉 G $블록$ 의 교차 그래프다. 어떤 그래프의 블록 그래프는 숲이다.; 3. 그래프 $G$ 의 블록컷(또는 블록컷포인트) 그래프는 초당적 그래프로, 한 partite 집합은 $G$ 의 컷-버티스로 구성되며, 다른 집합은 $G$ 의 $B_{i}$ 각 블록 $B_{i}$ $B_{i}$ ${\$ 에 $b_{i}$ 대해 정점 $b_{i}$ $b_{i}$ ${\$ displaystyle b_{i $}}}$ 가 있다. $G$ 가 연결되면 그 블록 컷포인트 그래프가 트리다.; 4. 블록 그래프(연결하면 클릭 트리라고도 하고 때로는 잘못해서 후시미 트리라고도 한다)는 블록이 모두 완전한 그래프인 그래프다. 포리스트는 블록 그래프로서, 특히 그래프의 블록 그래프는 블록 그래프로서, 모든 블록 그래프는 그래프의 블록 그래프로 구성될 수 있다.
bond: 최소 컷 세트: 제거가 그래프의 연결을 해제하는 가장자리 집합. 이 경우 적절한 부분 집합이 동일한 속성을 가지지 않는다.
book: 1. 책, 책 그래프 또는 삼각형 도서는 완전한 삼분법 $그래프 1,1, n$ K; 공유 가장자리에서 결합된 $n개$ 의 삼각형 집합체.; 2. 책이라고도 하는 또 다른 형태의 그래프는 가장자리 공유에서 결합된 4주기의 집합체, 가장자리가 있는 별의 데카르트 산물이다.; 3. 책 임베딩은 위상학 서적에 그래프를 내장한 것으로, 공유선을 따라 반플레인의 수집에 참여함으로써 형성된 공간이다. 보통 임베딩의 정점은 임베딩의 척추라고 하는 선상에 있어야 하며 임베딩의 가장자리는 책의 한 페이지인 단 반평면 안에 있어야 한다.
boundary: 1. 그래프를 내장한 상태에서 경계보행은 얼굴의 모든 입사 가장자리와 정점을 포함하는 서브그래프다.
bramble: Bramble은 서로 접촉하는 연결된 서브그래프의 모음으로, 두 개의 서브그래프가 정점을 공유하거나 각각 가장자리의 끝점을 포함하는 경우 터치한다. 브램블의 순서는 모든 하위 그래프와 비어 있지 않은 교차점이 있는 정점 집합의 가장 작은 크기이다. 그래프의 트리 너비는 그 버블의 최대 순서다.
branch-decomposition: $G$ 의 가지 형태는 $G$ 의 가장자리의 계층적 군집화인데, $G$ 의 가장자리로 라벨을 붙인 잎과 뿌리 없는 이진수로 표현된다. 분기 위치의 폭은 $e$ 로 구분된 두 하위 트리에서 $G$ 의 가장자리에 의해 결정된 하위 그래프 사이의 공유 정점 수의 최대, 이 이항 트리의 가장자리 $e$ 에 대한 것이다. $G$ 의 분기폭은 $G$ 의 모든 분기점 구성의 최소 폭이다.
branchwidth: 지점 구성을 참조하십시오.
bridge: 1. 브리지, isthmus 또는 절단 가장자리는 제거하면 그래프가 분리되는 가장자리. 브리지리스 그래프(bridgeless graph)는 브리지가 없는 그래프로서, 동등하게, 2개의 가장자리로 연결된 그래프다.; 2. 특히 평형성 시험의 맥락에서, 사이클의 브릿지는 사이클과 분리되고 각 두 가장자리가 사이클과 내부적으로 분리된 경로에 속하는 최대 서브그래프다. 화음은 단측교다. 주변 주기는 교량이 최대 한 개인 사이클이다. 그것은 그래프를 포함한 모든 평면도에서 면이어야 한다.; 3. 주기의 교량은 주기의 두 정점을 연결하지만 동일한 정점을 연결하는 주기의 어느 한 경로보다 짧은 경로를 의미하기도 한다. 브리지 그래프는 4개 이상의 꼭지점 사이클마다 브리지가 있는 그래프를 말한다.
bridgeless: 브리지리스 그래프(bridgeless graph)는 브리지 가장자리가 없는 그래프, 즉 2개의 가장자리가 연결된 그래프다.
butterfly: 1. 나비 그래프는 정점 5개와 가장자리 6개로 정점을 공유하는 두 개의 삼각형으로 형성된다.; 2. 나비 네트워크는 분산 컴퓨팅에서 네트워크 아키텍처로 사용되는 그래프로, 큐브 연결 사이클과 밀접한 관련이 있다.

C

C: $C$ 는_n n-vertex 주기 그래프 입니다. 주기를 참조하십시오.
cactus: 선인장 그래프, 선인장 나무, 선인장 나무 또는 후시미 나무는 각각의 가장자리가 최대 한 사이클에 속하는 연결된 그래프다. 그것의 블록은 주기 또는 단일 가장자리 이다. 게다가 각 꼭지점이 최대 두 블록에 속한다면, 그것은 크리스마스 선인장이라고 불린다.
cage: 케이지(cage)는 둘레에 대해 가능한 가장 작은 순서의 정규 그래프다.
canonical
canonization: 그래프의 표준 형태는 두 개의 그래프가 이형인 경우 및 이형인 경우에만 동일한 불변량을 갖는 불변성이다. 표준 형식은 표준 불변성 또는 완전한 불변성이라고도 할 수 있으며, 특정한 그래프 계열 내의 그래프에 대해서만 정의되기도 한다. 그래프 시성화는 표준 형태를 계산하는 과정이다.
card: 특히 재구성 추측의 맥락에서 하나의 꼭지점을 삭제하여 주어진 그래프에서 형성된 그래프. 그래프의 모든 카드의 멀티셋인 데크를 참조하십시오.
carving width: 조각 폭은 가지 폭과 유사하지만 가장자리의 계층적 군집 대신 정점의 계층적 군집을 사용하는 그래프 폭의 개념이다.
caterpillar: 애벌레 나무나 애벌레는 내부 마디가 길을 유도하는 나무를 말한다.
center: 그래프의 중심은 최소 편심률의 정점 집합이다.
chain: 1. 걸음걸이의 동의어.; 2. 대수적 위상으로부터 그래프에 방법들을 적용할 때, 체인 콤플렉스의 요소, 즉 정점 집합이나 가장자리 집합의 집합이다.
Cheeger constant: 확장을 참조하십시오.
cherry: 체리는 세 개의 꼭지점에 있는 길이다.^[7]
χ: $χ (G)$ (그리스 문자 기를 사용하는 것)은 G의 색수이고 $((G)$ 는 색지수(Chromatic index)이다. 색도와 색소를 참조하라.
child: 뿌리깊은 나무에서, $꼭지점$ v의 아이는 출출 가장자리를 따라 $v$ 의 이웃으로, 뿌리로부터 멀리 떨어져 있는 이웃이다.
chord
chordal: 1. 주기의 화음은 주기에 속하지 않는 에지로, 두 끝점이 모두 주기에 속한다.; 2. 화음 그래프는 4개 이상의 정점의 모든 주기가 화음을 가지므로 유일한 유도 주기는 삼각형이다.; 3. 강한 화음 그래프는 길이 6 이상의 모든 주기가 홀수 화음을 갖는 화음 그래프다.; 4. 화음 2차 그래프는 (숲이 아닌 한) 화음이 아니며, 6개 이상의 정점의 모든 사이클이 화음을 가지므로 유일한 유도 사이클은 4주기인 양분 그래프다.; 5. 원의 화음은 원의 두 점을 연결하는 선분할이다. 화음의 집합의 교차 그래프를 원 그래프라고 한다.
chromatic: 색칠하는 것과 관련이 있다; 색을 보라. 색도 그래프 이론은 그래프 색소 이론이다. 색수 $χ (G)$ 는 $G$ . $χ$ $'(G)$ 의 적정한 색상에 필요한 최소 $색수인$ G.의 적정한 가장자리 색상에 필요한 최소 색수인 G.
choosable
choosability: 그래프는 각 꼭지점에 k개의 $사용$ 가능한 색상 목록이 있을 때마다 목록 색상이 있으면 선택할 수 있다. 그래프의 선택성은 k-선택 가능한 가장 $작은$ k이다.
circle: 원 그래프(circle graph)는 원의 화음을 교차 그래프로 나타낸 것이다.
circuit: 회로는 폐쇄된 트레일 또는 사이클 공간의 요소(Ulerian spanning subgraph)를 가리킬 수 있다. 그래프의 회로 순위는 사이클 공간의 치수다.
circumference: 그래프의 원주는 가장 긴 단순 주기의 길이다. 그래프는 둘레가 순서와 같을 경우에만 해밀턴식이다.
class: 1. 그래프 또는 그래프 계열은 (대개 무한) 그래프의 집합으로, 종종 특정한 속성을 가진 그래프로 정의된다. 특별한 제약(예: 특정 집합에서 추출할 정점을 제한하고, 두 정점의 집합으로 에지를 정의하는 것)이 이루어지지 않는 한, 일반적으로 그래프 클래스의 클래스는 세트 이론을 사용하여 공식화할 때 설정되지 않기 때문에 "class"라는 단어가 "set"보다 사용된다.; 2. 색 그래프의 색 등급은 하나의 특정한 색을 가진 정점이나 가장자리의 집합이다.; 3. Vizing의 정리의 맥락에서, 간단한 그래프에 엣지 컬러링에 관하여, 색도 지수가 최대도와 같다면 1등급, 색도 지수가 1+1이면 2등급이라고 한다. 바이징의 정리대로라면 모든 간단한 그래프는 1등급이나 2등급이다.
claw: 발톱은 하나의 내부 꼭지점과 3개의 잎을 가진 나무 또는 동등하게 완전한 초당적 그래프 $K$ 를_1,3 의미한다. 발톱 없는 그래프는 발톱인 유도 서브그래프가 없는 그래프다.
clique: clique는 서로 인접한 정점 집합(또는 그 집합에 의해 유도된 완전한 하위 그래프)이다. 때때로 클릭은 상호 인접한 정점의 최대 집합(또는 최대 완전 서브그래프)으로 정의되며, 이러한 집합(또는 서브그래프)은 더 큰 집합(또는 서브그래프)에 속하지 않는다. k-clike는 order $k$ 의 집단이다. 그래프 $G$ 의 clique $number$ )( $G)$ 는 그 최대 clique의 순서다. clique graph는 최대 clique의 교차 그래프다. 완전한 초당적 하위 그래프인 biclique를 참조하십시오.
clique tree: 블록 그래프의 동의어.
clique-width: 그래프 $G$ 의 클라이크 폭은 라벨링된 정점을 만들고, 두 개의 라벨로 분리된 결합을 형성하며, 지정된 라벨로 모든 꼭지점 쌍을 연결하는 가장자리를 추가하거나, 지정된 라벨로 모든 정점을 다시 라벨링하는 연산을 통해 $G$ 를 구성하는 데 필요한 최소 고유 라벨 수입니다. 최대 $2개$ 의 clique-width 그래프는 정확히 cographs이다.
closed: 1. 폐쇄된 이웃은 그 중심 꼭지점을 포함하는 이웃이다. 이웃을 보라.; 2. 닫힌 걸음은 같은 꼭지점에서 시작하고 끝나는 걸음이다. 걷기를 참조하라.; 3. 그래프가 자신의 전이성 폐쇄와 같을 경우 전이성 폐쇄된다. transitive를 참조하십시오.; 4. 그래프에 대한 일부 연산에서는 그래프 속성이 닫히는데, 만일 연산에 대한 인수나 인수가 속성을 가질 때마다 그래프 속성이 닫힌다면, 그 결과도 그렇다. 예를 들어, 유전적 특성은 유도 하위 그래프에 의해 폐쇄되고, 단조로운 특성은 하위 그래프에 의해 폐쇄되며, 마이너 폐쇄 특성은 미성년자에 의해 폐쇄된다.
closure: 1. 지시된 그래프의 transitive closure에 대해서는 transitive를 참조하십시오.; 2. 방향 그래프의 닫힘은 닫힘 바깥의 정점에 나가는 가장자리가 없는 정점 집합이다. 예를 들어, 싱크대는 하나의 vertex 폐쇄다. 폐쇄 문제는 최소 또는 최대 중량의 폐쇄를 찾는 문제다.
co-: 이 접두사는 보통 보완 그래프를 포함하는 다양한 의미를 가지고 있다. 예를 들어, cograph는 보완을 포함하는 수술에 의해 생성된 그래프로, cocoloring은 각각의 꼭지점이 (적절한 색채에서와 같이) 독립된 세트나 (보수의 색채에서와 같이) 클릭을 유도하는 색소다.
color
coloring: 1. 그래프 색상은 주어진 색상 집합의 요소들에 의해 그래프의 정점을 표시하거나, 정점을 부분 집합으로 균등하게 구분하여 표시하는 것으로, 각 색상은 "색상 클래스"라고 불리며, 각 색상은 하나의 색상과 연관된다.; 2. 어떤 저자는 각 가장자리의 끝점에 다른 색을 할당하는 적절한 색상을 의미하기 위해 자격 없이 "색상"을 사용한다. 그래프 컬러링에서 목표는 가능한 한 적은 색상을 사용하는 적절한 색상을 찾는 것이다. 예를 들어, 초당적 그래프는 두 가지 색상으로만 색상이 있는 그래프인데, 네 가지 색 정리에서는 모든 평면 그래프는 최대 네 가지 색상으로 색칠할 수 있다고 명시하고 있다. 그래프는 $k$ 색으로 (적당하게) 색상을 한 경우 k 색상으로, 이것이 가능하다면 k 색상으로 또는 k 색상으로 된 것이라고 한다.; 3. 엣지 컬러링(끝점이 같은 두 개의 가장자리가 색을 공유하지 않도록 가장자리를 채색), 목록 컬러링(사용 가능한 색의 부분 집합으로 제한된 각 꼭지점과의 속성 컬러링), AC순환 컬러링(매 2색 서브그래프가 반복됨), 공동 컬러링(모든 색상 등급은 외설적인 색상을 유발함) 등 다양한 색상이 연구되었다.펜던트 세트 또는 클라이크), 전체 색상(모든 두 가지 색상 클래스는 가장자리를 공유함), 전체 색상(가장자리와 꼭지점 모두 색상이 있음); 4. 그래프의 컬러링 넘버는 1 더하기 퇴화. 그래프의 퇴행성 순서에 탐욕스러운 색소 알고리즘을 적용하면 이 정도의 색상을 최대한 많이 사용하기 때문에 그렇게 불린다.
comparability: 비방향 그래프는 정점이 부분 순서 집합의 요소이고 두 정점이 부분 순서로 유사할 때 인접한 경우 비교가능성 그래프다. 동등하게 비교가능성 그래프는 전이적 방향을 갖는 그래프다. 다른 많은 종류의 그래프는 특별한 유형의 부분 순서의 비교가능성 그래프로 정의될 수 있다.
complement: 단순 그래프 $G$ 의 보완 ${\bar {G}}$ 그래프 ${\$ 는 $G$ 와 동일한 정점에 있는 또 다른 그래프로서 $G$ 에 인접하지 않은 두 꼭지점에 대한 에지가 있다.
complete: 1. 전체 그래프는 두 꼭지점마다 인접한 그래프로서 존재할 수 있는 모든 가장자리가 존재한다. 정점이 $없는$ 완전한 그래프는 $종종 n$ K로 표시된다. 완전한 초당적 그래프는 정점 분할의 반대편에 있는 정점 두 개가 각각 인접해 있는 그래프를 말한다. 칸막이의 한 $쪽$ 에 정점이 있고 다른 쪽에 $b$ 정점이 있는 완전한 양립자 그래프는 종종 $K$ 로_a,b 표시된다. 동일한 용어와 표기법이 전체 다중 사이트 그래프에도 확장되었으며, 정점이 세 개 이상의 하위 집합으로 나뉘고 다른 하위 집합의 모든 정점 쌍이 인접해 있는 그래프. 하위 집합의 정점 수가 $a,$ $b,$ $c, ...$ 인 경우 이 그래프는 $K$ 로_{a, b, c, ...} 표시된다.; 2. 주어진 그래프의 완성은 어느 정도 원하는 성질을 가진 슈퍼그래프다. 예를 들어, 화음 완성은 화음 그래프인 슈퍼그래프다.; 3. 완전한 일치는 완벽한 일치를 뜻하는 동의어다. 일치를 참조하라.; 4. 완전한 색상은 각각의 색 쌍이 적어도 하나의 가장자리의 끝점에 사용되는 적절한 색이다. 최소한의 색상을 가진 모든 색상은 완성되지만, 더 많은 색상을 가진 완전한 색상이 존재할 수 있다. 그래프의 무채색 수는 완전한 색상의 최대 색상 수입니다.; 5. 그래프의 완전한 불변성은 표준형식의 동의어로서, 비이성형 그래프의 값이 다른 불변형이다.
component: 그래프의 연결된 구성요소는 최대 연결 서브그래프다. 이 용어는 또한 쌍방향 연결 구성요소, 삼방향 연결 구성요소 및 강하게 연결된 구성요소를 포함하여 어느 정도 높은 연결 순서를 가진 그래프 정점의 최대 하위 그래프 또는 하위 집합에도 사용된다.
condensation: 방향 그래프 $G$ 의 응축은 $G$ 의 각 강하게 연결된 성분에 대해 하나의 꼭지점이 있는 방향의 아세클릭 그래프와 $G$ 에서 적어도 하나의 가장자리의 두 끝점을 포함하는 성분의 쌍을 연결하는 에지 연결 그래프다.
cone: 범용 꼭지점을 포함하는 그래프.
connect: 연결해야 할 원인.
connected: 연결된 그래프는 각 꼭지점 쌍이 경로의 끝점을 형성하는 그래프다. 더 높은 연결 형태에는 지시된 그래프에서의 강력한 연결성(각 두 꼭지점에 대해 양방향으로 한 꼭지점에서 다른 쪽까지의 경로가 있음), k-Vertex로 연결된 그래프( $k$ vertes보다 적은 경우 그래프를 분리할 수 없음), k-edge로 연결된 그래프( $k$ edge보다 적은 경우 그래프를 분리할 수 없음)가 포함된다.
converse: 역 그래프는 전치 그래프의 동의어다. 전치 그래프를 참조하라.
core: 1. k-core는 $k$ 보다 작은 모든 정점, 그리고 초기 제거 후 $k$ 보다 작은 모든 정점을 제거하여 형성된 유도 서브그래프다. 퇴폐를 보다.; 2. 중심은 $G$ 에서 그 자체로 모든 그래프 동형성이 이형성이라는 그래프 G이다.; 3. 그래프 $G$ 의 핵심은 $최소$ $그래프$ $H$ 로 G에서 H까지 동형성이 존재하며 그 반대의 경우도 존재한다. $H$ 는 이소모르프만큼 독특하다. $G$ 의 유도 서브그래프로 나타낼 수 있으며, 그 모든 자기동형성이 이형화라는 의미에서 핵심이다.; 4. 그래프 일치 이론에서 그래프의 핵심은 모든 최대 일치의 결합으로 형성된 둘마지-멘델손 분해의 한 측면이다.
cotree: 1. 스패닝 트리의 보완재.; 2. cograph를 기술하는 데 사용되는 뿌리깊은 나무 구조로, 각 cograph 정점은 나무의 잎이며, 나무의 각 내부 노드는 0 또는 1로 표시되며, 두 cograph 정점은 나무에서 가장 낮은 공통 조상이 1로 표시된 경우에만 인접한다.
cover: 꼭지점 커버는 그래프의 모든 가장자리에 발생하는 정점 집합이다. 가장자리 커버는 그래프의 모든 꼭지점에 입사하는 가장자리 집합이다. 그래프의 조합(정점 및 가장자리)이 그래프와 같을 경우 그래프의 하위 그래프 집합이 해당 그래프를 덮는다.
critical: 주어진 속성에 대한 임계 그래프는 속성이 있지만 단일 꼭지점을 삭제하여 형성된 모든 하위 그래프에는 속성이 없다. 예를 들어, 요인 임계 그래프는 모든 꼭지점 삭제에 대해 완벽한 일치(1-요인)를 가지는 그래프지만 (정점 수가 홀수이기 때문에) 완벽한 일치 자체가 없다. 속성은 없지만 모든 단일 버텍스 삭제에 사용되는 그래프를 비교하십시오.
cube
cubic: 1. 큐브 그래프, 큐브의 꼭지점과 가장자리를 나타내는 8-Vertex 그래프.; 2. 하이퍼큐브 그래프, 큐브 그래프의 고차원 일반화.; 3. 접힌 입방체 그래프, 반대쪽 정점을 연결하는 일치점을 추가하여 하이퍼큐브로부터 형성한다.; 4. 하이퍼큐브 그래프의 반제곱인 반제곱 그래프.; 5. 하이퍼큐브의 거리를 보존하는 서브그래프인 부분 큐브.; 6. 그래프 $G$ 의 세제곱은 그래프 검정력 $G$ 이다³.; 7. 입방 그래프, 3-정규 그래프의 다른 이름이며, 각 정점에 3개의 입사 모서리가 있다.; 8. 입방체 연결 주기, 하이퍼큐브의 각 꼭지점을 사이클로 교체하여 형성된 입방 그래프.
cut
cut-set: 컷(cut)은 그래프의 정점을 두 개의 하위 집합으로 분할하거나, 세트가 비어 있지 않은 경우 그러한 분할 영역에 걸쳐 있는 가장자리의 집합(cut-set이라고도 함)을 의미한다. 두 하위 집합에 끝점이 있으면 가장자리가 파티션에 걸쳐 있다고 한다. 따라서 연결된 그래프에서 컷 세트를 제거하면 컷 세트가 분리된다.
cut point: 연결점을 참조하십시오.
cut space: 그래프의 절단 공간은 그래프의 절단 세트를 요소로 하고 세트의 대칭적 차이를 벡터 추가 연산으로 하는 GF(2) 벡터 공간이다.
cycle: 사이클은 폐쇄된 보행(투어를 여행이라고도 함)을 의미하거나, 정점을 반복하지 않고 결과적으로 가장자리(단순 사이클이라고도 함)를 제외한 폐쇄된 보행(closed walk)을 의미할 수 있다. 어느 경우든, 첫 번째 꼭지점의 선택은 보통 중요하지 않은 것으로 간주된다: 보행의 주기 순열은 동일한 주기를 생성한다. 중요한 사이클의 특별한 경우로는 그래프의 둘레를 정의하는 해밀턴 사이클, 유도 사이클, 말초 사이클, 최단 사이클 등이 있다. k 사이클은 길이 $k$ 의 사이클이다. 예를 들어 2 사이클은 디건이고 3 사이클은 삼각형이다. 사이클 그래프는 그 자체로 단순한 사이클이며, $정점$ 이 없는 사이클 그래프는 일반적으로 $C$ 로_n 표시된다. 사이클 공간은 그래프의 단순한 사이클에 의해 생성되는 벡터 공간이다.

D

DAG: 지시된 순환 그래프, 지시된 주기가 없는 지시된 그래프에 대한 약어.
deck: 특히 재구성 추측의 맥락에서 가능한 모든 방법으로 단일 꼭지점을 삭제하여 단일 그래프 $G$ 에서 형성된 그래프 다중 집합. 엣지 데크는 모든 가능한 방법으로 단일 가장자리를 삭제함으로써 같은 방식으로 형성된다. 갑판에 있는 그래프는 카드라고도 불린다. 또한 중요(어떤 카드에도 속성이 없는 그래픽) 및 저자(모든 카드에 속성이 없는 그래픽)를 참조하십시오.
decomposition: 트리 분해, 경로 분해 또는 분기 배치를 참조하십시오.
degenerate
degeneracy: k-degenerate 그래프는 모든 유도 하위 그래프가 최대 $k$ 까지 최소도를 갖는 비방향 그래프다. 그래프의 퇴행성은 k-degenerate인 가장 작은 $k$ 이다. 퇴행순서는 각 꼭지점이 유도 하위 그래프와 모든 후행 정점을 갖는 정점의 순서다. k-degenate 그래프의 퇴행순서에서 모든 정점들은 후행선 대부분의 정점을 $가지고$ 있다. Degeneration은 k-core 수, 너비, 연결로도 알려져 있으며, 1 더하기 퇴행성은 컬러링 번호 또는 Szekeres–Wilf 번호로도 불린다. k-degenate 그래프는 k-interval graph로도 불린다.
degree: 1. 그래프에서 정점의 정도는 입사 에지의 수입니다.^[2] 그래프 $G$ (또는 그 최대도)는 정점도의 최대치로, 흔히 $Δ(G$ )로 표시되며 $,$ $최소$ G는 정점도의 최소치로, 흔히 $Δ (G$ )로 표시된다 $.$ 정도를 valency라고 부르기도 한다. $G$ 에서 $v$ 의 정도를 $d G (v),$ $d (G$ ),d( $v)$ 로 나타낼 수 있다 $.$ 총도는 모든 정점의 도 합이다. 손떨림 보조정리기는 짝수다. 도 순서는 모든 정점의 도(道)를 가장 큰 것부터 가장 작은 것까지 정렬하여 모은 것이다. 지시된 그래프에서 인도(입력 에지 수)와 아웃도(출발 에지 수)를 구별할 수 있다.^[2]; 2. 그래프의 동형성 정도는 그 하드와이거 숫자와 동의어로, 가장 큰 패거리 마이너의 순서다.
Δ, δ: $Δ(G)$ (그리스 문자 델타 사용)는 G $단위$ 의 정점 최대 정도이며, $Δ (G)$ 는 최소 정도(도 참조).
density: n개 노드의 그래프에서 밀도는 n개 노드의 전체 그래프에서 그래프 에지 수에 대한 그래프 에지 수의 비율이다. 고밀도 그래프를 참조하십시오.
depth: 루트 트리에서 노드의 깊이는 루트부터 노드까지의 경로에 있는 가장자리 수입니다. 예를 들어, 루트의 깊이는 0이고 인접 노드 중 하나의 깊이는 1이다. 노드에서 1을 뺀 수준이다. 그러나 일부 저자들은 그 대신 깊이를 노드 수준의 동의어로 사용한다는 점에 유의한다.^[8]
diameter: 연결된 그래프의 직경은 최단 경로의 최대 길이다. 즉, 그래프에서 정점 쌍 사이의 거리의 최대값이다. 그래프의 가장자리에 무게가 있는 경우, 그래프의 가중 직경은 경로를 따라 가장자리 무게의 합으로 경로 길이를 측정하고, 가중되지 않은 직경은 가장자리 수로 경로 길이를 측정한다. 연결이 끊긴 그래프의 경우 정의는 다양하다. 직경은 무한으로 정의되거나 연결된 성분의 가장 큰 직경으로 정의되거나 정의되지 않을 수 있다.
diamond: 다이아몬드 그래프는 네 개의 꼭지점과 다섯 개의 가장자리를 가진 비방향 그래프다.
diconnected: 강하게 연결됨. (분리된 상태와 혼동되지 않음)
digon: digon은 지시된 그래프나 다중 글자로 길이가 2인 간단한 순환을 말한다. digon은 동일한 에지를 두 번 반복해야 하기 때문에 단순한 비방향 그래프에서는 발생할 수 없으며 이는 단순성의 정의를 위반한다.
digraph: 지시된 그래프의 동의어.^[2]
dipath: 지시된 경로를 참조하십시오.
direct predecessor: 머리가 주어진 꼭지점인 방향 가장자리의 꼬리.
direct successor: 꼬리가 주어진 꼭지점인 방향 가장자리의 머리.
directed: 방향 그래프는 가장자리가 한 꼭지점에서 다른 꼭지점까지 구별되는 방향을 갖는 그래프다.^[2] 혼합 그래프에서 지시된 가장자리는 다시 구별된 방향을 갖는 가장자리인데, 지시된 가장자리는 호 또는 화살표라고도 할 수 있다.
directed arc: 화살표를 참조하십시오.
directed edge: 화살표를 참조하십시오.
directed line: 화살표를 참조하십시오.
directed path: 모든 가장자리의 방향이 같은 경로. 방향 경로가 꼭지점 $x$ 에서 $꼭지점$ y로 이어지는 경우 $x$ 는 $y$ 의 전임자, $y$ 는 x의 후계자, $y$ 는 $x$ 에서 도달할 수 있다고 한다.
direction: 1. 그래프에서 인접한 두 정점 사이의 비대칭 관계, 화살표로 표현된다.; 2. 방향 경로에서 두 꼭지점 사이의 비대칭 관계.
disconnect: 연결이 끊어진 원인.
disconnected: 연결되지 않음.
disjoint: 1. 두 개의 서브그래프는 가장자리를 공유하지 않으면 가장자리 분리, 정점을 공유하지 않으면 꼭지점 분리다.; 2. 두 개 이상의 그래프의 분리 결합은 정점과 가장자리 집합이 해당 집합의 분리 결합인 그래프다.
distance: 그래프에서 두 꼭지점 사이의 거리는 두 꼭지점이 끝점으로 있는 최단 경로의 길이입니다.
domatic: 그래프의 domatic 파티션은 정점을 지배하는 집합으로 나누는 파티션이다. 그래프의 도미 숫자는 그러한 파티션에서 최대 지배적인 집합 수입니다.
dominating: 지배적인 집합은 그래프의 모든 정점을 포함하거나 인접한 정점 집합이다.정점 표지와 혼동해서는안 된다. 정점 집합은 그래프의 모든 가장자리에서 발생하는 정점 집합이다. 중요한 특별한 유형의 지배 집합은 독립 지배 집합(독립 집합이기도 한 지배 집합)과 연결된 지배 집합(연결된 서브그래프를 유도한 지배 집합)이 있다. 단일 vertex 지배적인 세트를 범용 꼭지점이라고도 할 수 있다. 그래프의 지배 번호는 가장 작은 지배 집합의 정점 수입니다.

E

E: $E (G)$ 는 $G$ 의 에지 집합이다. 에지 집합을 참조한다.
ear: 그래프의 귀는 끝점이 일치할 수 있지만 그렇지 않으면 정점이나 가장자리가 반복되지 않는 경로를 의미한다.
ear decomposition: 귀 분해는 그래프의 가장자리를 일련의 귀로 분할하는 것으로, 각 끝점(첫 번째 끝점 이후)은 이전 귀에 속하고 내부 지점은 이전 귀에 속하지 않는다. 열린 귀는 단순한 경로(정점 반복이 없는 귀)이며, 열린 귀의 분해는 첫 번째 귀 뒤의 각 귀는 열려 있는 귀의 분해로, 그래프는 양쪽 귀의 연결이 되어 있는 경우에만 열린 귀의 분해로 이루어진다. 귀는 가장자리 수가 홀수일 경우 홀수이고, 홀수 귀 분해는 각 귀가 홀수일 경우 귀 분해이며, 그래프는 인자에 중요한 경우에만 홀수 귀 분해된다.
eccentricity: 정점의 편심성은 정점에서 다른 정점까지의 가장 먼 거리다.
edge: 가장자리는 그래프를 구성하는 두 가지 기본 단위 중 하나이다. 각 가장자리에는 끝점이라고 불리는 두 개의 정점(또는 하이퍼그래프, 더 많은)이 있다. 가장자리는 방향을 지시하거나 방향을 조정하지 않을 수 있으며, 방향을 지정하지 않은 가장자리는 선이라고도 하며, 방향된 가장자리는 호 또는 화살표라고도 한다. 방향을 지정하지 않은 단순 그래프에서 가장자리는 정점의 집합으로 나타낼 수 있으며, 지시된 단순 그래프에서는 정점의 순서가 지정된 쌍으로 나타낼 수 있다. $꼭지점$ $x$ 와 y를 연결하는 가장자리가 $xy$ 로 표기되기도 한다.
edge cut: 제거가 그래프의 연결을 끊는 가장자리 집합. 한쪽 가장자리 절단은 다리, 이스트무스 또는 절단 가장자리라고 불린다.
edge set: 주어진 그래프 $G$ 의 가장자리 집합이며, $때로는$ E $(G$ )로 표시되기도 한다 $.$
edgeless graph: 주어진 정점 집합에서 에지가 없는 그래프 또는 완전히 분리된 그래프는 에지가 없는 그래프다. 빈 그래프라고도 하지만 이 용어는 정점이 없는 그래프를 가리킬 수도 있다.
embedding: 그래프 내장(Graph inmbedding)은 그래프를 점으로 나타내는 위상학적 공간의 부분 집합으로, 각 정점은 곡선의 끝점으로 가장자리의 끝점이 있는 곡선으로 나타내며, 정점이나 가장자리 사이의 다른 교차점은 없다. 평면 그래프는 유클리드 평면에 그러한 내장형 그래프를 말하며, 토로이드 그래프는 토러스(torus)에 그러한 내장형 그래프를 말한다. 그래프의 속은 그것을 삽입할 수 있는 2차원 다지관의 최소 가능한 속이다.
empty graph: 1. 비어 있지 않은 정점 집합의 가장자리 없는 그래프.; 2. 정점이 없고 가장자리가 없는 그래프, 순서 영점 그래프.
end: 무한 그래프의 끝은 광선의 등가 등급으로, 두 개의 광선이 두 개의 정점으로부터 무한히 많은 정점을 포함하는 세 번째 광선이 있을 경우 등가선이다.
endpoint: 주어진 가장자리로 연결된 두 개의 꼭지점 중 하나 또는 산책로, 산책로 또는 경로의 첫 번째 또는 마지막 꼭지점 중 하나. 지정된 가장자리의 첫 번째 끝점을 꼬리라고 하고 두 번째 끝점을 머리라고 한다.
enumeration: 그래프 열거는 주어진 그래프 클래스의 그래프를 순서의 함수로 계산하는 문제다. 보다 일반적으로 열거형 문제는 특정 종류의 결합형 개체(예: 군집, 독립형 집합, 색상 또는 스패닝 트리)를 계산하거나 알고리즘적으로 모든 개체를 나열하는 문제를 나타낼 수 있다.
Eulerian: 오일러 길은 그래프의 모든 가장자리를 정확히 한 번 사용하는 걸음이다. 오일러 서킷(Ulerian cycle 또는 오일러 투어라고도 함)은 모든 가장자리를 정확히 한 번 사용하는 폐쇄된 보행이다. 오일러 그래프는 오일러 회로를 가진 그래프다. 비방향 그래프의 경우, 이는 그래프가 연결되어 있고 모든 꼭지점에 고른 정도가 있음을 의미한다. 지시된 그래프의 경우, 이것은 그래프가 강하게 연결되어 있고 모든 꼭지점이 도 단위와 동일하다는 것을 의미한다. 접속 요건이 느슨해지는 경우도 있으며, 정도 요건만 만족하는 그래프를 오일리언이라고 한다.
even: 예를 들어, 짝수 사이클은 길이가 짝수인 사이클이다.
expander: 익스팬더 그래프는 에지 확장, 정점 확장 또는 스펙트럼 확장이 0에서 멀리 떨어진 그래프다.
expansion: 1. 그래프 $G$ 의 에지 확장, 등측수 수 또는 치거 상수는 최소 비율로, $G$ 의 정점의 거의 절반에 있는 부분 집합 $S$ 에 대한 최소 $비율$ 이며, S에서 정점 수로 S를 남기는 에지 수의 최소 비율이다.; 2. 그래프 $G$ 의 정점 확장, 정점 등정점 수 또는 확대는 $최소$ 비율이며, G의 정점의 거의 절반에 해당하는 부분 집합 $S$ 에 대한 $최소$ 비율이며, S의 정점 수에 $S$ 에 인접한다.; 3. 그래프 $G$ 의 고유 인접 확장은 $G$ 의 정점의 절반에 해당하는 부분 집합에 걸쳐 $S$ 의 바깥쪽 정점 수에 $인접$ 하지만 S의 $고유$ 정점에 인접한 정점 수의 최소 비율이다.; 4. d-정규 그래프 $G$ 의 스펙트럼 확장은 인접행렬 중 가장 큰 고유값 $d$ 와 두 번째로 큰 고유값 사이의 스펙트럼 간극이다.; 5. 모든 r-shallow Minor가 $r$ 의 함수에 의해 경계된 정점에 대한 에지 대 정점의 비율을 갖는 경우, $r$ 의 함수가 다항식인 경우 다항식 확장성을 갖는 그래프군은 경계 확장성을 가지고 있다.

F

face: 평면 그래프 또는 그래프 포함에서, 그래프와 분리된 포함면의 부분 집합 또는 표면의 연결된 구성요소. 비행기에 임베딩하는 경우, 한 얼굴을 제외한 모든 얼굴이 경계될 것이다; 무한대로 확장되는 하나의 예외적인 얼굴을 바깥 면이라고 한다.
factor: 그래프의 요인은 스패닝 서브그래프: 그래프의 모든 정점을 포함하는 서브그래프다. 이 용어는 주로 정규 하위 그래프의 맥락에서 사용된다: k-요인은 k-정규인 요인이다. 특히 1인자는 완벽한 매칭과 같은 것이다. 인자 임계 그래프는 꼭지점 하나를 삭제하면 1-요인이 있는 그래프가 생성되는 그래프를 의미한다.
factorization: 그래프 인자화는 그래프의 가장자리를 인자로 분할하는 것이고, k-요인화는 k-요인으로 분할하는 것이다. 예를 들어 1-요인화는 각 정점이 각 색의 가장자리로 입사되는 추가 특성을 가진 가장자리 색소다.
family: 수업의 동의어.
finite: 그래프는 정점의 수가 유한하고 가장자리 수가 유한하면 유한하다. 많은 출처는 명시적으로 말하지 않고 모든 그래프가 유한하다고 가정한다. 그래프는 각 정점에 입사 에지 수가 한정되어 있는 경우 국소적으로 유한하다. 무한 그래프(infinite graph)는 유한하지 않은 그래프로서, 정점이 무한히 많거나, 에지가 무한히 많거나, 둘 다 있다.
first order: 그래프의 첫 번째 순서 논리는 변수가 그래프의 정점을 나타내는 논리의 일종으로, 정점 두 개가 인접해 있는지 여부를 검정하는 이항 술어가 존재한다. 변수가 정점 또는 가장자리의 집합을 나타낼 수 있는 두 번째 순서 로직과 구별된다.
-flap: 정점 X $집합$ 의 경우 X-플랩은 $X$ 를 삭제하여 형성된 유도 서브그래프의 연결된 구성요소다. 플랩 용어는 작은 정점 세트를 플랩에 매핑하는 기능인 안식처의 맥락에서 일반적으로 사용된다. 주기 정점의 플랩 또는 주기의 화음인 주기 교량도 참조한다.
forbidden: 금지 그래프 특성은 하위 그래프, 유도 하위 그래프 또는 미성년자 그래프로서 특정한 다른 그래프를 가지고 있지 않은 그래프로서 그래프 계열의 특성을 나타내는 것이다. $H$ 가 서브그래프, 유도 서브그래프, 마이너스로 발생하지 않는 그래프 중 하나라면 $H$ 는 금지된다고 한다.
forest: 숲은 사이클이 없는 비방향 그래프(뿌리지 않은 나무의 분리 결합) 또는 뿌리깊은 나무들의 분리 결합으로 형성된 방향 그래프다.
Frucht: 1. 로버트 프루히트; 2. 비교 대칭이 없는 두 개의 가장 작은 입방 그래프 중 하나인 Frucht 그래프.; 3. 모든 유한집단은 유한 그래프의 대칭집합이라는 Frucht의 정리.
full: 유도된 것과 동의어.
functional graph: 기능 그래프는 모든 꼭지점에 아웃도가 있는 방향 그래프다. 마찬가지로 기능 그래프는 최대 지시의 사이비숲이다.

G

G: 그래프를 나타내는 데 자주 사용되는 변수.
genus: 그래프의 속은 내포될 수 있는 표면의 최소 속이다. 내포 참조.
geodesic: 명사로서 지오데틱은 가장 짧은 길의 동의어다. 형용사로 사용할 경우 최단 경로 또는 최단 경로 거리와 관련된 것을 의미한다.
giant: 랜덤 그래프 이론에서 거대 성분은 그래프의 정점의 일정한 부분을 포함하는 연결된 성분이다. 랜덤 그래프의 표준 모형에는 일반적으로 최대 하나의 거대한 성분이 있다.
girth: 그래프의 둘레는 최단 주기의 길이다.
graph: 그래프 이론에서 연구의 기본 목적, 가장자리별로 쌍으로 연결된 정점 시스템. 가장자리의 방향성 여부에 따라 지시된 그래프 또는 방향성이 없는 그래프로 세분되는 경우가 많다. 혼합 그래프에는 두 가지 유형의 가장자리가 모두 포함된다.
greedy: 탐욕스러운 알고리즘에 의해 생산된다. 예를 들어, 그래프의 탐욕스러운 색상은 어떤 순서로 정점을 고려하고 각 꼭지점에 사용 가능한 첫 번째 색상을 할당함으로써 생성되는 색이다.
Grötzsch: 1. 허버트 그뢰츠슈; 2. 그뢰츠슈 그래프, 적절한 색상으로 4가지 색상을 필요로 하는 가장 작은 삼각형 없는 그래프.; 3. 삼각 프리 평면 그래프는 항상 최대 3가지 색상으로 채색할 수 있다는 그뢰츠슈의 정리.
Grundy number: 1. 그래프의 그룬디 수는 탐욕스러운 색에 의해 생성되는 최대 색상으로, 정점 순서가 좋지 않다.

H

H: 특히 다른 그래프가 이미 $G$ 로 표시된 경우 그래프를 나타내는 데 자주 사용되는 변수.
H-coloring: 그래프 $G$ (여기서 $H$ 도 그래프)의 H-색상은 $H$ 에서 $G$ 까지의 동형상이다.
H-free: $H$ 에 대한 유도 서브그래프 이형성이 없는 경우, 즉 $H$ 가 금지된 유도 서브그래프인 경우 그래프는 H가 없는 것이다. H-프리 그래프는 H-프리 그래프인 모든 그래프(또는 종종 모든 유한 그래프)의 집합이다.^[9] 예를 들어 삼각형이 없는 그래프는 삼각형 그래프를 하위 그래프로 포함하지 않는 그래프다. H-프리라는 재산은 항상 유전적이다. 그래프는 $H$ 에 대한 경미한 이형성이 없는 경우 H-소형성이 없다.
Hadwiger: 1. 휴고 하드와이거; 2. 그래프의 Hadwiger 번호는 그래프의 가장 큰 전체 부차의 순서다. 수축계수 또는 동형성 정도라고도 한다.; 3. 하드와이거 추측이란 하드와이거 숫자가 결코 색수보다 작지 않다는 추측이다.
Hamiltonian: 해밀턴 경로 또는 해밀턴 사이클은 단순한 스패닝 경로 또는 단순한 스패닝 사이클로, 그래프의 모든 정점을 정확히 한 번 다룬다. 그래프는 해밀턴 사이클을 포함하는 경우 해밀턴이고, 해밀턴 경로를 포함하는 경우 추적 가능하다.
haven: k-헤이븐은 $k$ 정점 이하의 모든 세트 $X$ 를 플랩 중 하나에 매핑하는 기능으로, 종종 추가적인 일관성 조건을 만족시킨다. 안식처의 순서는 $숫자$ k이다. Havense는 유한 그래프의 트리 너비와 끝 및 무한 그래프의 Hadwiger 숫자의 특성을 나타내는 데 사용될 수 있다.
height: 1. 뿌리가 있는 나무에서 노드의 높이는 그 노드에서 시작하여 잎으로 끝나는 루트(즉, 그 노드의 깊이가 엄격히 증가함)에서 멀어지는 최대 경로의 가장자리 수입니다.; 2. 뿌리나무의 높이는 뿌리의 높이다. 즉 나무의 높이는 뿌리에서 시작하여 잎으로 끝나는, 가능한 가장 긴 경로의 가장자리 수입니다.; 3. 지시된 악순환 그래프의 높이는 이 그래프에서 지시된 경로의 최대 길이 입니다.
hereditary: 그래프의 유전적 특성은 유도 하위 그래프에 의해 닫히는 속성이다. $G$ 가 유전적 특성을 가지고 있다면 $G$ 의 모든 유도 하위 그래프도 그래프를 비교해야 한다. 단조(모든 하위 그래프에 닫힘) 또는 마이너 폐쇄(미성년자에 닫힘).
hexagon: 정확히 6개의 가장자리와 6개의 꼭지점으로 구성된 단순한 사이클.
hole: 구멍은 길이 4 이상의 유도 사이클이다. 홀수 구멍은 홀수 길이의 구멍이다. 안티홀은 순서 4의 유도 하위그래프로서, 보완이 사이클이다. 동등하게, 보완 그래프의 구멍이다. 이 용어는 주로 완벽한 그래프의 맥락에서 사용되는데, 홀수 구멍이나 홀수 안티홀이 없는 그래프라는 점에서 완벽한 그래프 정리가 강한 것이 특징이다. 구멍이 없는 그래프는 화음 그래프와 같다.
homomorphic equivalence: 두 개의 그래프는 각 그래프에서 다른 그래프까지 두 개의 동형성이 존재한다면 동형상 등가물이다.
homomorphism: 1. 그래프 동형성은 한 그래프의 꼭지점 집합에서 다른 그래프의 꼭지점 집합까지 매핑하여 인접한 정점을 인접한 정점에 매핑하는 것이다. 이러한 유형의 그래프 간 매핑은 그래프 이론에 대한 범주-이론적 접근방식에서 가장 일반적으로 사용되는 것이다. 적절한 그래프 색상은 완전한 그래프에 대한 동형성으로 동등하게 묘사될 수 있다.; 2. 그래프의 동형성 정도는 그 하드와이거 숫자와 동의어로, 가장 큰 패거리 마이너의 순서다.
hyperedge: 그래프의 가장자리에 정확히 두 개의 끝점이 있어야 하는 요구 사항과 대조적으로, 끝점이 여러 개 있는 하이퍼그래프의 가장자리.
hypercube: 하이퍼큐브 그래프는 기하학적 하이퍼큐브의 꼭지점과 가장자리에서 형성된 그래프다.
hypergraph: 하이퍼그래프는 각 가장자리(이 맥락에서 축성이라고 함)가 두 개 이상의 끝점을 가질 수 있는 그래프를 일반화한 것이다.
hypo-: 이 접두사는 그래프 속성과 함께 속성은 없지만 단일 꼭지점을 삭제하여 형성된 모든 하위 그래프에 속성이 있는 그래프를 나타낸다. 예를 들어, 저자극 그래프는 해밀턴 사이클이 없지만, 모든 1Vertex 삭제 시 해밀턴 서브그래프가 생성되는 그래프다. 속성을 가지고 있지만 모든 단일 버텍스 삭제에는 사용되지 않는 그래프에 사용되는 중요도를 비교하십시오.^[10]

I

in-degree: 지시된 그래프에서 들어오는 가장자리 수입니다. 정도를 참조하십시오.
incidence: 그래프의 발생률은 꼭지점이 가장자리의 끝점인 정점-끝 쌍이다.
incidence matrix: 그래프의 입사 행렬은 행이 그래프의 정점에 의해 인덱싱되고, 열이 가장자리에 의해 인덱싱되는 행렬로, $정점$ i와 $에지$ j가 인시던트인 경우 $행$ i와 $컬럼$ j에 대한 셀에 있는 행렬이고, 그렇지 않으면 0이다.
incident: 가장자리와 끝점 중 하나 사이의 관계.^[2]
incomparability: 비교가능성 그래프는 비교가능성 그래프를 보완한 것이다. 비교가능성을 참조하라.
independent: 1. 독립형 집합은 엣지 없는 서브그래프를 유도하는 정점 집합이다. 안정 세트 또는 누에고치라고도 할 수 있다. 독립 번호 $α (G)$ 는 최대 독립 집합의 크기다.; 2. 그래프의 그래픽 매트로이드에서 해당 서브그래프가 나무나 숲인 경우 가장자리의 부분집합은 독립적이다. 2두근자성모형에서, 해당 서브그래프가 사이비숲인 경우 가장자리의 부분집합은 독립적이다.
indifference: 무관심 그래프는 적절한 간격 그래프 또는 단위 간격 그래프의 다른 이름이다. 적절한 이름을 참조하십시오.
induced: 그래프의 유도 하위그래프 또는 전체 하위그래프는 정점의 부분 집합과 부분 집합에 양쪽 끝점이 있는 모든 가장자리에서 형성된 하위그래프다. 특별한 경우로는 유도 경로 및 유도 주기, 유도 경로 또는 주기인 유도 서브그래프가 있다.
inductive: 타락의 동의어.
infinite: 무한 그래프는 유한하지 않은 그래프다. 유한함을 보라.
internal: 길이나 나무의 꼭지점은 잎이 아닌 경우 내측이다. 즉, 그 정도가 하나보다 크면 내측이다. 두 길은 처음과 마지막 것을 제외하고 공통의 꼭지점이 없다면 내적으로 분리된다(일부 사람들은 그것을 독립이라고 부른다).
intersection: 1. 두 그래프의 교차점은 가장 큰 공통 서브그래프로서, 두 그래프에 속하는 정점과 가장자리에 의해 형성된 그래프다.; 2. 교차로 그래프는 정점이 세트나 기하학적 객체에 해당하는 그래프로, 해당 두 세트나 객체에 비빈 교차점이 있을 때 정확히 두 정점 사이에 가장자리가 있다. 여러 등급의 그래프는 특정 유형의 객체에 대한 교차 그래프로 정의될 수 있다. 예를 들어, 코드 그래프(나무 하위 트리의 횡단 그래프), 원 그래프(원형 화음의 횡단 그래프), 구간 그래프(선 간격의 횡단 그래프), 선 그래프(그래프의 가장자리의 횡단 그래프) 및 clique graphs(그래프의 최대 cliques를 나타내는 그래프). 모든 그래프는 집합의 일부 패밀리에 대한 교차로 그래프인데, 이 패밀리를 그래프의 교차로 표현이라고 한다. 그래프 $G$ 의 교차로 번호는 $G$ 의 교차로 표현에서 요소의 최소 총 수입니다.
interval: 1. 구간 그래프는 선의 구간을 교차 그래프로 나타낸 것이다.; 2. 그래프에서 간격 $[u,$ $v]$ 은 $u$ 에서 $v$ 까지의 모든 최단 경로의 조합이다.; 3. 간격두께는 경로폭과 동의어다.
invariant: 재산의 동의어.
inverted arrow: 다른 화살표에 비해 방향이 반대인 화살표. 화살표 $(y,$ $x)$ 는 화살표 $(x,$ y)의 반전 화살표다 $.$
isolated: 그래프의 절연 정점은 0, 즉 입사 모서리가 없는 정점이다.^[2]
isomorphic: 두 그래프 사이에 이형성이 있으면 이형성이 있다. 이형성을 참조하라.
isomorphism: 그래프 이형성은 한 그래프의 정점과 가장자리가 다른 그래프의 정점과 가장자리의 일치성을 보존하는 일대일 발생이다. 이와 관련된 두 개의 그래프는 이형체라고 한다.
isoperimetric: 확장을 참조하십시오.
isthmus: 제거가 그래프의 연결을 끊는 가장자리 의미에서의 브리지의 동의어.

K

K: 전체 그래프, 전체 쌍방향 그래프 및 전체 다중 표준 그래프의 표기법은 완료를 참조하십시오.
κ: $κ (G)$ (그리스 문자 카파 사용)은 $G$ 에서 최대 클라이크의 순서다. clique를 참조하라.
kernel: 지시된 그래프의 커널은 안정적이고 흡수적인 정점의 집합이다.
knot: 지시된 그래프의 피할 수 없는 섹션. 매듭(수학) 및 매듭 이론을 참조하십시오.

L

L: $L (G)$ 은 $G$ 의 선 그래프 입니다. 선을 참조하십시오.
label: 1. 그래프의 꼭지점 또는 가장자리와 관련된 정보. 레이블이 붙은 그래프는 꼭지점이나 가장자리가 레이블을 갖는 그래프다. 정점 레이블 또는 가장자리 레이블을 사용하여 그래프의 개체 중 레이블이 있는 개체를 지정할 수 있다. 그래프 라벨링은 특정 제약조건에 따라 그래프에 라벨을 할당하는 여러 가지 다른 문제를 가리킨다. 레이블이 색으로 해석되는 그래프 색상을 참조하십시오.; 2. 그래프 열거의 맥락에서, 그래프의 정점들은 모두 서로 구별할 수 있으면 라벨을 붙였다고 한다. 예를 들어, 정점과 정수의 1부터 그래프 순서까지의 일대일 대응관계를 고정함으로써 이것이 사실이라고 할 수 있다. 정점에 라벨이 붙으면 서로 이형성이지만 정점 순서가 다른 그래프는 별도의 개체로 계산된다. 이와는 대조적으로, 정점들이 라벨을 붙이지 않은 경우, 서로 이형화된 그래프들은 별도로 계산되지 않는다.
leaf: 1. 잎 꼭지점이나 펜던트 꼭지점(특히 나무에서)은 정도가 $1인$ 꼭지점이다. 잎 가장자리 또는 펜던트 가장자리는 잎 꼭지점을 하나의 이웃에 연결하는 가장자리다.; 2. 나무의 잎 권력은 정점이 나무의 잎이며, 가장자리가 나무의 거리가 주어진 한계점인 잎을 연결한 그래프를 말한다.
length: 가중치가 없는 그래프에서 주기, 경로 또는 보도의 길이는 사용하는 가장자리 수입니다. 가중치 그래프에서 이 값은 대신 사용하는 가장자리의 가중치 합계가 될 수 있다. 길이는 그래프에서 두 꼭지점 사이의 최단 경로, 둘레(가장 짧은 주기 길이) 및 가장 긴 경로를 정의하는 데 사용된다.
level: 1. 일부에서는^[11] 깊이의 동의어로 정의하지만, 이것은 노드 플러스 1의 깊이다. 루트 트리에서 노드의 수준은 루트부터 노드까지의 경로에 있는 노드 수입니다. 예를 들어, 루트는 레벨 1을 가지며, 인접한 노드 중 하나는 레벨 2를 가진다.; 2. 레벨이나 깊이가 같은 모든 노드의 집합.^[11]
line: 비방향 가장자리의 동의어. 그래프 $G$ 의 선 그래프 $L (G)$ 은 $G$ 의 각 에지에 대한 정점과 $G$ 의 끝점을 공유하는 각 에지 쌍에 대한 에지가 있는 그래프다.
linkage: 타락의 대명사.
list: 1. 인접 목록은 그래프 알고리즘에 사용하기 위한 그래프의 컴퓨터 표현이다.; 2. 목록 색상은 각 꼭지점에 사용 가능한 색의 목록이 있는 그래프 색상의 변형이다.
local: 그래프의 로컬 속성은 그래프에서 정점의 인접성에 의해서만 결정되는 속성이다. 예를 들어, 그래프는 모든 이웃이 유한하다면 국부적으로 유한하다.
loop: 루프 또는 자체 루프(self-loop)는 양쪽 끝점이 동일한 가장자리 입니다. 길이 $1$ 의 순환을 이룬다. 이것들은 간단한 그래프에서는 허용되지 않는다.

M

magnification: 정점 확장의 동의어.
matching: 일치는 두 사람이 정점을 공유하지 않는 가장자리 집합이다. 정점은 일치에서 가장자리의 끝점 중 하나일 경우 일치하거나 포화된다. 완벽한 일치 또는 완전한 일치는 모든 꼭지점과 일치하는 일치로서, 1-요인이라고도 불릴 수 있으며, 순서가 일정할 때만 존재할 수 있다. 거의 완벽에 가까운 일치는, 홀수 순서가 있는 그래프에서, 하나의 꼭지점을 제외한 모든 것을 포화시키는 것이다. 최대 일치는 가능한 많은 에지를 사용하는 일치를 말하며, 그래프 $G$ 의 일치 번호 $αα (G)$ 는 최대 일치의 에지 수입니다. 최대 일치는 추가 에지를 추가할 수 없는 일치를 의미한다.
maximal: 1. 주어진 그래프 $G$ 의 하위그래프는 그 속성을 가지고 있지만 $G$ 의 하위그래프인 다른 수퍼그래프가 없는 경우 특정 속성에 대해 최대치가 된다. 즉, 그것은 재산과 함께 서브그래프의 최대 요소다. 예를 들어, 최대 클라이크는 더 큰 완전한 서브그래프로 확장될 수 없는 완전한 서브그래프다. "최대"라는 단어는 "최대"와 구별되어야 한다: 최대 하위 그래프는 항상 최대적이지만, 반드시 그 반대는 아니다.; 2. 주어진 속성을 가진 단순 그래프는 그래프와 속성의 단순성을 모두 유지하면서 더 이상 에지를 추가할 수 없는 경우(정점 세트의 변경 없이 유지) 해당 속성에 대해 최대치가 된다. 따라서 예를 들어 최대 평면 그래프는 에지를 더 추가하면 비 평면 그래프가 생성될 수 있는 평면 그래프다.
maximum: 주어진 그래프 $G$ 의 하위 그래프는 특정 속성을 가진 모든 하위 그래프 중 가장 큰 하위 그래프(순서 또는 크기별)인 경우 특정 속성에 대해 최대값이다. 예를 들어, 최대 클릭은 주어진 그래프에서 가장 큰 클릭 중 하나이다.
median: 1. 정점 세 개의 중위수, 특히 중위수 그래프와 모듈형 그래프에서 정점의 모든 쌍 사이의 최단 경로에 속하는 정점.; 2. 중위수 그래프는 꼭지점 세 개마다 고유한 중위수를 갖는 그래프를 말한다.
Meyniel: 1. 앙리 메이니엘, 프랑스 그래프 이론가; 2. 메이니엘 그래프는 길이 5 이상의 홀수 사이클마다 적어도 2개의 화음을 갖는 그래프다.
minimal: 지정된 그래프의 하위 그래프는 특정 속성이 있지만 적절한 하위 그래프가 없는 경우 특정 속성에 대해 최소값이다. 즉, 그것은 재산에 대한 하위 그래프의 최소 요소다.
minimum cut: 컷 세트가 최소 총 중량을 갖는 컷으로, 지정된 꼭지점 쌍을 분리하는 컷으로 제한될 수 있다. 컷 세트는 최대 흐름 최소 컷 정리로 특징지어진다.
minor: $G$ 에서 가장자리 또는 정점을 삭제하고 $G$ 에서 가장자리를 수축시켜 $H$ 를 얻을 수 있다면 그래프 $H$ 는 다른 그래프 $G$ 의 부차다. $H$ 의 정점을 형성하도록 수축된 $G$ 의 서브그래프가 모두 작은 직경을 가질 정도로 마이너로서 형성될 수 있다면 그것은 얕은 마이너다. $H$ 는 $G$ 가 $H$ 의 하위분할인 하위분할을 갖는 $경우$ G의 위상학적 부전위로서 H가 $없는$ 경우 H-미너(H-minor)가 된다. 그래프 제품군은 미성년자에 의해 폐쇄될 경우 마이너 클로즈업된다. 로버슨-시모어 정리는 미성년자 폐쇄형 가정은 금지된 미성년자 집단이 유한한 것으로 특징지어진다.
mixed: 혼합 그래프는 지시된 가장자리와 간접되지 않은 가장자리를 모두 포함할 수 있는 그래프다.
modular: 1. 모듈형 그래프, 정점의 각 세 쌍이 세 쌍의 모든 쌍 사이의 최단 경로에 속하는 중앙 정점 하나 이상을 갖는 그래프.; 2. 모듈식 분해, 모든 정점이 동일한 방식으로 그래프의 나머지 부분에 연결되는 서브그래프로 그래프를 분해하는 것.; 3. 그래프 클러스터링의 모듈성, 기대값과 교차 클러스터 에지 수의 차이.
monotone: 그래프의 단일 속성(monotone properties)은 하위 그래프에 의해 닫히는 속성이다. $G$ 가 유전적 속성을 가지고 $있다면$ G의 모든 하위 그래프도 마찬가지여야 한다. 유전적 특성(유도 하위 그래프에 따라 닫힘) 또는 마이너 닫힘(미성년자에 닫힘)을 비교한다.
Moore graph: 무어 그래프는 무어 바운드와 정확히 일치하는 정규 그래프다. 무어 바운드는 에드워드 F에 의해 증명된 그래프의 정도, 지름, 순서와 관련된 불평등이다. 무어, 모든 무어 그래프는 우리야
multigraph: 다중 글자는 다중 보조(그리고 자주 자체 루프)를 허용하는 그래프로서, 단순할 필요가 없는 그래프다.
multiple adjacency: 다중 인접 또는 다중 에지는 모두 동일한 끝점을 갖는 둘 이상의 에지 집합이다(방향은 동일, 지시된 그래프의 경우). 가장자리가 여러 개인 그래프를 흔히 다중그래프라고 부른다.
multiplicity: 가장자리의 다중성은 다중 인접성에 있는 가장자리의 수입니다. 그래프의 다중성은 가장자리의 최대 다중성이다.

N

N: 1. 개방 및 폐쇄된 이웃에 대한 표기법은 이웃을 참조한다.; 2. 소문자 $n$ 은 (특히 컴퓨터 공학에서) 주어진 그래프의 정점 수를 나타내기 위해 자주 사용된다.
neighbor
neighbour: 주어진 꼭지점에 인접한 꼭지점.
neighborhood
neighbourhood: 꼭지점 $v$ 의 열린 이웃(또는 이웃)은 $v$ 에 인접한 모든 정점에 의해 유도된 하위 그래프다. 폐쇄적인 이웃은 동일한 방식으로 정의되지만 $v$ 그 자체도 포함한다. $G$ 에서 $v$ 의 개방된 근방은 $N G (v)$ 또는 $N (v)$ 로 표기할 수 있으며, $폐쇄$ 된_G $근방$ 은N[ $v$ ] 또는 N $[v$ ]로 표기할 수 있다 $.$ 동네의 개방성이나 폐쇄성을 특정하지 않을 때에는 개방성을 전제로 한다.
network: 속성(예: 이름)이 노드 및/또는 가장자리와 연결된 그래프.
node: 꼭지점의 동의어.
non-edge: 비 에지 또는 반 에지는 인접하지 않은 정점 쌍으로, 보완 그래프의 가장자리.
null graph: 빈 그래프를 참조하십시오.

O

odd: 1. 홀수 사이클은 길이가 홀수인 사이클이다. 비-비-비-바타이트 그래프의 홀수 둘레는 가장 짧은 홀수 사이클의 길이다. 홀수홀은 홀수 사이클의 특별한 경우로, 유도되고 4개 이상의 정점을 갖는 홀수 사이클이다.; 2. 홀수 꼭지점은 정도가 홀수인 정점이다. 핸드셰이킹 보조기구에 의해 모든 유한한 비방향 그래프는 짝수 수의 홀수 정점을 가진다.; 3. 홀수 귀는 가장자리 수가 홀수인 단순한 경로 또는 단순한 사이클로, 인자 임계 그래프의 홀수 귀 분해에 사용된다. 귀 참조.; 4. 홀수 화음은 짝수 사이클에서 홀수 거리인 두 정점을 연결하는 가장자리를 말한다. 홀수 화음은 강한 화음 그래프를 정의하는데 사용된다.; 5. 홀수 그래프는 Kneser 그래프의 특별한 경우로서, 각 ( $n$ - 1 $)-$ element set의 ( $2n$ - 1 $)-$ element set에 대해 하나의 꼭지점이 있고, 해당 집합이 분리되었을 때 두 하위 집합을 연결하는 가장자리가 있다.
open: 1. 이웃을 보라.; 2. 걸음걸이를 보라.
order: 1. 그래프 $G$ 의 순서는 정점수 $V(G)$ 로, 이 수량에 n 변수를 사용하는 $경우$ 가 많다. 가장자리 수 크기도 참조하십시오.; 2. 그래프의 로직의 한 종류. 첫 번째 순서와 두 번째 순서를 참조하라.; 3. 그래프의 순서나 순서는 특히 위상학적 순서(모든 가장자리가 순서의 초기 꼭지점에서 나중 꼭지점으로 가는 지시된 악순환 그래프의 순서)와 퇴행 순서(각 정점이 유도된 서브그레이에서 최소도를 갖는 순서)의 맥락에서 정점을 배열한 것이다.ph 및 모든 이후 정점).; 4. 안식처나 브램블의 순서는 안식처와 브램블을 참조한다.
orientation
oriented: 1. 비방향 그래프의 방향은 가장자리에 방향을 할당하여 지시된 그래프로 만드는 것이다. 방향 그래프는 방향이 지정된 그래프다. 따라서 예를 들어, 폴리 트리는 지향적인 나무로, 가장자리 방향에 일관성이 요구되지 않는다는 점에서 지시된 트리(수목)와 다르다. 다른 특별한 형태의 오리엔테이션에는 토너먼트, 완전한 그래프의 방향, 강한 방향, 강하게 연결된 방향, 악순환 방향, 악순환 방향, 오일러 방향, 오일러 방향, 그리고 전치적으로 닫힌 전이 방향 등이 포함된다.; 2. 방향 그래프, 일부 저자들이 지시된 그래프의 동의어로 사용한다.
out-degree: 학위를 참조하다.
outer: 얼굴을 보다.
outerplanar: 외부 평면 그래프는 모든 정점이 그래프의 바깥 면에 있도록 평면(교차 없음)에 삽입할 수 있는 그래프다.

P

path: 경로는 출처에 따라 반복된 정점이 없는 보행 또는 보행일 수 있으며, 결과적으로 가장자리(단순 경로라고도 함)가 될 수 있다. 중요한 특수 사례로는 유도 경로와 최단 경로를 들 수 있다.
path decomposition: 그래프 $G$ 의 경로 분해는 기본 트리가 경로인 트리 분해다. 그것의 너비는 나무 분해와 같은 방식으로 정의되며, 가장 큰 가방 크기보다 작은 것으로 정의된다. $G$ 경로 분해의 최소 폭은 $G$ 의 경로 폭이다.
pathwidth: 그래프 $G$ 의 경로 폭은 $G$ 의 경로 분해의 최소 폭이다. $그것$ 은 또한 G의 간격 완료의 clique 숫자로 정의될 수 있다. 그것은 항상 $G$ 의 대역폭과 트리 너비 사이에 있다. 구간 두께, 꼭지점 분리 번호 또는 노드 검색 번호로도 알려져 있다.
pendant: 나뭇잎을 보라.
perfect: 1. 완벽한 그래프는 모든 유도 서브그래프에서 색소수가 클라이크 숫자와 같은 그래프다. 완벽한 그래프 정리와 강한 완벽한 그래프 정리는 완벽한 그래프에 대한 두 가지 이론으로, 전자는 완벽한 그래프라는 것을 증명하고 후자는 홀수 구멍이나 안티홀이 없는 그래프라는 것을 증명한다.; 2. 완벽하게 순서가 가능한 그래프는 이 순서가 있는 탐욕스러운 컬러링 알고리즘이 모든 유도 서브그래프를 최적으로 색칠하는 방식으로 정점을 순서가 가능한 그래프를 말한다. 완벽하게 주문 가능한 그래프는 완벽한 그래프의 하위 클래스다.; 3. 완벽한 매칭은 모든 정점을 포화시키는 매칭이다. 매칭을 참조하라.; 4. 완벽한 1-요인화는 그래프의 가장자리를 완벽한 일치로 분할하여 각 두 개의 일치점이 해밀턴 사이클을 형성하도록 하는 것이다.
peripheral: 1. 주변 사이클 또는 비분리 사이클은 교량이 최대 1개인 사이클이다.; 2. 말초 정점은 편심률이 최대인 정점이다. 나무에서, 이것은 나뭇잎임에 틀림없다.
Petersen: 1. 줄리어스 피터슨(1839~1910), 덴마크의 그래프 이론가.; 2. Petersen 그래프, 10-Vertex 15-edge 그래프, counterrexample로 자주 사용된다.; 3. 브릿지리스 큐빅 그래프마다 완벽하게 일치한다는 피터슨의 정리
planar: 평면 그래프는 유클리드 평면에 내장된 그래프다. 평면 그래프는 특정 임베딩이 이미 고정된 평면 그래프를 말한다. k-평면 그래프는 엣지당 $교차점$ 이 최대 k인 평면에서 그릴 수 있는 그래프다.
polytree: 폴리 트리는 방향 트리를 의미하며, 마찬가지로 방향성이 있는 시계열 그래프로서, 방향성이 있는 그래프의 밑부분이 트리인 것이다.
power: 1. 그래프 $G$ 의 그래프 검정력 $G$ 는^k 동일한 정점에 있는 또 다른 그래프로서, 두 정점이 $G$ 에서 대부분의 $k$ 에서 거리에 있을 때 $G$ 에^k 인접해 있다. 잎 검정력은 나무의 잎에 의해 유도된 하위 그래프를 취함으로써 나무의 검정력으로부터 파생된, 밀접한 관련성이 있는 개념이다.; 2. 파워그래프 분석은 네트워크 내의 패거리, 바이클릭, 별 등을 파악하여 복잡한 네트워크를 분석하는 방법이다.; 3. 무규모 네트워크의 정도 분포에서의 전력법칙은 일정한 정점수가 정도의 힘에 비례하는 현상이다.
predecessor: 지정된 경로에서 지정된 꼭지점 앞에 오는 꼭지점.
proper: 1. 적절한 하위 그래프는 전체 그래프에 대해 적어도 하나의 꼭지점이나 가장자리를 제거하는 하위 그래프를 말한다. 유한한 그래프의 경우 적절한 하위 그래프는 전체 그래프에 대해 결코 이형적이지 않지만 무한 그래프의 경우 그럴 수 있다.; 2. 적절한 색상은 각 가장자리의 끝점에 다른 색을 할당하는 그래프(색상)의 정점에 색을 할당하는 것이다. 색 참조.; 3. 적절한 구간 그래프 또는 적절한 원형 호 그래프는 구간이나 호가 다른 구간이나 호를 포함하지 않도록 (존중적으로) 구간의 집합 또는 원형 호를 나타내는 교차 그래프다. 적절한 구간 그래프를 단위 구간 그래프(항상 단위 구간으로 나타낼 수 있기 때문에) 또는 무관심 그래프라고도 한다.
property: 그래프 속성은 일부 그래프에 대해 진실일 수 있고 다른 그래프에 대해 거짓일 수 있으며, 이는 그래프 구조에만 의존하며 레이블과 같은 부수적인 정보에 의존하지 않는다. 그래프 속성은 그래프 클래스(특정 특성을 가진 그래프) 단위로 동등하게 설명될 수 있다. 보다 일반적으로 그래프 속성은 또한 그래프의 크기, 순서 또는 정도 순서와 같은 부수적인 정보와 다시 무관한 그래프의 함수일 수 있다. 이렇게 속성의 보다 일반적인 정의를 그래프의 불변량이라고도 한다.
pseudoforest: 사이비 포리스트는 연결된 각 구성 요소가 최대 한 사이클을 갖는 비방향 그래프 또는 각 정점이 최대 하나의 나가는 가장자리를 갖는 방향 그래프입니다.
pseudograph: 필적( is self)은 자가 루핑이 가능한 그래프 또는 다중 글씨를 말한다.

Q

quasi-line graph: 준선 그래프 또는 국소 공동 이파르타트 그래프는 모든 정점의 열린 근방을 두 개의 구획으로 분할할 수 있는 그래프다. 이 그래프들은 항상 발톱이 없고 특별한 경우 선 그래프를 포함한다. 그것들은 발톱이 없는 그래프의 구조 이론에 사용된다.
quiver: 부들부들란 범주 이론에서 사용되는 지시된 다중 글씨를 말한다. 부들부들 가장자리는 화살이라고 한다.

R

radius: 그래프의 반경은 정점의 최소 편심률이다.
Ramanujan: 라마누잔 그래프는 스펙트럼 확장이 가능한 한 큰 그래프를 의미한다. 즉 인접 행렬의 고유값이 최대 $2{\sqrt {d-1}}$ - $(\$ 인 d-정규 그래프다.
ray: 무한 그래프에서 광선은 끝점이 정확히 하나 있는 무한 단순 경로다. 그래프의 끝은 광선의 등가 등급이다.
reachability: 그래프 내에서 한 꼭지점에서 다른 꼭지점으로 이동하는 기능.
reachable: 긍정적인 도달 가능성을 가지고 있다. 꼭지점 $y$ 는 $x$ 에서 y까지의 경로가 존재하는 경우 꼭지점 $x$ 에서 도달할 수 있다고 한다.
recognizable: 재구성 추측의 맥락에서 그래프 속성은 그래프의 데크에서 진위를 파악할 수 있다면 알아볼 수 있다. 많은 그래프 속성이 인식 가능한 것으로 알려져 있다. 재구성 추측이 사실이라면 모든 그래프 속성을 인식할 수 있다.
reconstruction: 재구성 추측에 따르면, 각 비방향 $그래프$ G는 모든 가능한 $방법$ 으로 G에서 하나의 꼭지점을 제거하여 형성된 그래프의 다중 집합인 데크에 의해 고유하게 결정된다. 이런 맥락에서 재구성은 갑판에서 그래프를 구성하는 것이다.
rectangle: 정확히 네 개의 가장자리와 네 개의 꼭지점으로 구성된 간단한 사이클.
regular: 그래프는 모든 꼭지점에 $도$ d가 있을 때 d-규칙이다. 정규 그래프는 일부 $d$ 에 대해 d-정규적인 그래프다.
regular tournament: 정규 토너먼트는 모든 정점에 있어서 학위가 아웃도어인 토너먼트다.
reverse: 전치사를 참조하십시오.
root: 1. 그래프의 지정 꼭지점, 특히 지시된 나무와 뿌리 그래프에서 지정된다.; 2. 그래프 검정력에 대한 역방향 연산: $그래프$ G의 k번째 루트(k번째 루트)는 두 꼭지점이 $G$ 에 인접한 동일한 정점 집합의 다른 그래프로서, 두 꼭지점이 뿌리에서 최대 $k$ 의 거리를 갖는 경우에만 그러하다.

S

second order: 그래프의 두 번째 순서 논리는 변수가 정점, 에지, 정점 집합 및 (때로는) 에지 집합을 나타낼 수 있는 논리의 한 형태다. 이 논리에는 정점과 가장자리가 인시던트인지 테스트하기 위한 술어와 정점 또는 가장자리가 집합에 속하는지 여부를 포함한다. 변수가 정점만 나타낼 수 있는 첫 번째 순서 논리와는 구별된다.
saturated: 일치 항목을 참조하십시오.
searching number: 노드 검색 번호는 경로 폭과 동의어다.
self-loop: 루프의 동의어.
separating vertex: 연결점을 참조하십시오.
separation number: 정점 분리 번호는 경로 폭과 동의어다.
simple: 1. 단순 그래프는 루프가 없고 다중 보조성이 없는 그래프다. 즉, 각 가장자리는 두 개의 서로 다른 끝점을 연결하며 두 가장자리는 동일한 끝점을 가지지 않는다. 단순 가장자리는 다중 인접성의 일부가 아닌 가장자리다. 많은 경우에 그래프는 달리 명시되지 않는 한 단순하다고 가정한다.; 2. 단순경로나 단순주기는 정점이 반복되지 않고 결과적으로 에지가 반복되지 않는 경로나 사이클이다.
sink: 방향 그래프에서 싱크(sink)는 나가는 가장자리가 없는 정점이다(out-di는 0이다).
size: 그래프 $G$ 의 크기는 가장자리 수 $E(G)$ 이며,^[12] 변수 $m$ 은 이 수량에 자주 사용된다. 정점 수 순서도 참조하십시오.
small-world network: 소세계 네트워크는 대부분의 노드가 서로의 이웃이 아니지만, 대부분의 노드는 소수의 홉이나 스텝으로 다른 모든 노드에서 도달할 수 있는 그래프다. 구체적으로, 소세계 네트워크는 무작위로 선택된 두 노드 사이의 일반적인 거리 L(필요한 단계 수)이 네트워크에서 노드 N의 수의 로그에 비례하여 증가하는 그래프로 정의된다.
snark: 스나크는 색도 지수가 4와 같은 단순하고 연결되고 브리지가 없는 입방 그래프다.
source: 지시된 그래프에서 소스는 수신 에지가 없는 정점이다(도는 0이다).
space: 대수 그래프 이론에서 이항장 위의 여러 벡터 공간은 그래프와 연관될 수 있다. 각각은 벡터에 대한 에지 또는 정점 집합과 벡터 합 연산으로 집합의 대칭적 차이를 가진다. 가장자리 공간은 모든 가장자리 집합의 공간이며, 꼭지점 공간은 모든 꼭지점 집합의 공간이다. 절단 공간은 그래프의 절단 세트를 요소로 하는 가장자리 공간의 하위 공간이다. 사이클 공간은 오일러 스패닝 서브그래프를 그 요소로 가지고 있다.
spanner: 스패너(spanner)는 최단 경로 거리가 밀집 그래프나 다른 메트릭 공간의 거리와 근접한 (일반적으로 희박한) 그래프다. 변형으로는 기하학적 스패너, 기하학적 공간에서 꼭지점이 점인 그래프, 그래프 거리와 근접한 그래프의 스패너, 그리고 원래 그래프의 거리와 근접한 밀도 그래프의 희박한 서브그래프인 그래프 스패너 등이 있다. 탐욕 스패너란 탐욕스러운 알고리즘에 의해 만들어진 그래프 스패너로, 일반적으로 모든 가장자리를 최단부터 최장까지 고려하며 거리 근사치를 보존하는 데 필요한 것을 유지한다.
spanning: 서브그래프는 주어진 그래프의 모든 정점을 포함할 때 확장된다. 중요한 경우로는 스패닝 트리, 스패닝 서브그래프, 스패닝 서브그래프, 스패닝 서브그래프 등이 있다. 스패닝 서브그래프는 인자로도 불릴 수 있는데, 특히 (하지만 그뿐만 아니라) 정규적인 경우에는 인자로 불릴 수 있다.
sparse: 희소성 그래프는 정점 수에 비해 가장자리가 거의 없는 그래프다. 일부 정의에서는 주어진 그래프의 모든 하위 그래프에 대해서도 동일한 속성이 참이어야 한다.
spectral
spectrum: 그래프의 스펙트럼은 인접 행렬의 고유값 집합이다. 스펙트럼 그래프 이론은 그래프를 분석하기 위해 스펙트럼을 사용하는 그래프 이론의 한 분야다. 스펙트럼 확장을 참조하십시오.
split: 1. 분할 그래프는 정점을 클라이크와 독립 집합으로 분할할 수 있는 그래프를 말한다. 관련 등급의 그래프인 이중 분할 그래프는 강력한 완벽한 그래프 정리의 증거에 사용된다.; 2. 임의 그래프의 분할은 그 정점을 두 개의 비어 있지 않은 하위 집합으로 분할하는 것으로, 이 절단을 가로지르는 가장자리가 완전한 양분적 하위 그래프를 형성하도록 한다. 그래프의 분할은 분할 분해라고 불리는 나무 구조로 나타낼 수 있다. 스플릿은 다른 스플릿에 의해 교차되지 않을 때 강한 스플릿이라고 불린다. 분할은 양쪽의 꼭지점이 둘 이상일 때 불연속이라고 불린다. 그래프는 비종교적 분할이 없을 때 prime이라고 불린다.
square: 1. 그래프 $G$ 의 제곱은 그래프 검정력 $G$ 이고², 다른 방향에서 $G$ 는 $G$ 의² 제곱근이다. 양분 그래프의 반제곱은 양분 그래프의 한쪽이 유도하는 제곱의 하위 그래프다.; 2. 사각형 그래프는 모든 경계면이 4 사이클이고 모든 정도 ≤ 3의 정점이 바깥 면에 속하도록 그려질 수 있는 평면 그래프를 말한다.; 3. 사각 격자 그래프는 단위 길이 가장자리로 연결된 정수 좌표를 가진 평면의 점으로부터 정의한 격자 그래프다.
stable: 안정된 세트는 독립 세트의 동의어다.
star: 별은 하나의 내부 꼭지점이 있는 나무로, 동등하게, 일부 $n$ ≥ $2$ 에 대한 완전한 쌍방향 그래프 $K$ 이다_1,n. 잎이 세 개 달린 별의 특별한 경우를 발톱이라고 한다.
strength: 그래프의 강도는 가능한 모든 제거에 대해 그래프에서 제거된 가장자리 수의 최소 비율이다. 이는 정점 제거에 기초한 강도와 유사하다.
strong: 1. 강력한 연결성 및 지시된 그래프의 강하게 연결된 구성 요소는 연결된 구성 요소 및 구성 요소를 참조하십시오. 강한 방향은 강하게 연결된 방향이다. 방향을 참조하라.; 2. 강력한 완벽한 그래프 정리를 위해서는 완벽함을 보라.; 3. 강하게 규칙적인 그래프는 인접한 두 정점마다 공유 이웃의 수가 같고 비인접 정점마다 공유 이웃의 수가 동일한 정규 그래프를 말한다.; 4. 강한 화음 그래프는 길이 6 이상의 고른 주기마다 이상한 화음을 갖는 화음 그래프다.; 5. 강하게 완벽한 그래프는 유도된 모든 서브그래프가 모든 최대 분열을 만족하는 독립적인 집합을 갖는 그래프다. 메이니엘 그래프는 "매우 완벽하다"라고 불리기도 하는데, 그 안에서 모든 꼭지점이 그러한 독립적인 집합에 속하기 때문이다.
subforest: 숲의 서브그래프.
subgraph: 그래프 $G$ 의 하위 그래프는 $G$ 의 정점과 가장자리의 부분 집합에서 형성된 또 다른 그래프다. 정점 부분 집합은 가장자리 부분 집합의 모든 끝점을 포함해야 하지만 추가 정점을 포함할 수도 있다. 스패닝 서브그래프는 그래프의 모든 정점을 포함하는 것이고, 유도 서브그래프는 엔드포인트가 정점 부분 집합에 속하는 모든 가장자리를 포함하는 것이다.
subtree: 하위 트리는 나무의 연결된 하위 그래프다. 때때로, 뿌리깊은 나무의 경우, 하위 트리는 선택한 꼭지점에서 도달할 수 있는 모든 정점과 가장자리로 형성되는 연결된 하위 그래프의 특별한 유형으로 정의된다.
successor: 지정된 경로에서 지정된 꼭지점 뒤에 오는 꼭지점.
superconcentrator: 초집중기는 정점 $I$ 과 $O$ 의 두 개의 지정되고 동일한 크기의 서브셋이 있는 그래프로, $I$ 와 T $O$ 의 두 개의 동일한 크기의 $서브셋$ 에 대해 $S$ 의 모든 정점과 $T$ 의 정점을 연결하는 연결 해제 경로군이 존재한다. 또한 일부 공급원은 초집중기가 I를 $공급원$ 으로 하고 $O$ 를 싱크대로 하는 방향의 순환 그래프일 것을 요구한다.
supergraph: 지정된 그래프에 정점, 가장자리 또는 둘 모두를 추가하여 만든 그래프. $H$ 가 $G$ 의 서브그래프라면 $G$ 는 $H$ 의 수퍼그래프다.

T

theta: 1. 세타 그래프는 동일한 두 개의 뚜렷한 끝 정점을 갖는 세 개의 내부 분리(단순) 경로의 결합이다.^[14]; 2. 유클리드 평면의 점 집합의 세타 그래프는 각 점을 둘러싸고 있는 원뿔 시스템을 구성하고 원뿔의 중심선에 투영하는 것이 가장 작은 점에 원뿔당 하나의 가장자리를 추가함으로써 구성된다.; 3. 그래프의 Lovász number 또는 Lovász theta 함수는 clique number와 관련된 그래프 불변량이며, 세미데핀 프로그래밍에 의해 다항식 시간으로 계산될 수 있다.
Thomsen graph: Thomsen 그래프는 전체 초당적 그래프 $K_{3,3}$ $K_{3,3}$ , $K_{3,3}$ ${\$ 의 이름이다 $K_{3,3}$
topological: 1. 위상학 그래프는 그래프의 정점과 가장자리를 평면 내 점 및 곡선으로 표현한 것이다(교차를 피할 필요는 없음).; 2. 위상적 그래프 이론은 그래프 임베딩에 관한 학문이다.; 3. 위상학적 정렬은 각 가장자리가 시퀀스의 초기 정점에서 후기 정점으로 이동하는 정점 순서인 위상학적 순서로 지시된 아세클릭 그래프를 배열하는 알고리즘적 문제다.
totally disconnected: 엣지 없는 것과 동의어.
tour: 닫힌 오솔길, 같은 꼭지점에서 시작하고 끝나는 산책로, 반복된 가장자리가 없다. 오일러 투어는 모든 그래프 가장자리를 사용하는 투어다. 오일러 투어를 참조하십시오.
tournament: 토너먼트는 완전한 그래프의 방향이다. 즉, 두 꼭지점이 정확히 하나의 방향의 가장자리로 연결되도록(두 꼭지점 사이의 두 방향 중 하나만 이동) 지시된 그래프다.
traceable: 추적 가능한 그래프는 해밀턴 경로를 포함하는 그래프다.
trail: 반복된 모서리가 없는 걷기.
transitive: 전이적 재산과 관련이 있는 것. 지정된 그래프의 전이성 폐쇄는 원래 그래프가 동일한 두 꼭지점을 연결하는 경로를 가질 때마다 한 꼭지점에서 다른 꼭지점으로 에지를 갖는 동일한 꼭지점 집합의 그래프다. 그래프의 타동성 감소는 동일한 타동성 폐쇄를 갖는 최소 그래프인데, 방향 Acyclc 그래프는 독특한 타동성 감소를 가진다. Transitive 방향은 자체 Transitive closure인 그래프의 방향이며, 비교가능성 그래프를 위해서만 존재한다.
transpose: 주어진 방향 그래프의 전치 그래프는 동일한 정점에 있는 그래프인데, 각 가장자리는 방향을 반대로 한다. 그래프의 역 또는 역이라고도 할 수 있다.
tree: 1. 트리는 연결된 것과 순환하는 것 둘 다인 비방향 그래프 또는 하나의 꼭지점(나무의 뿌리)에서 나머지 모든 정점까지 독특한 보행이 존재하는 방향 그래프다.; 2. k-트리(k-tree)는 공유 k-clik에 붙임 $(k$ + $1)-$ 크리크를 함께 붙임으로써 형성된 그래프다. 통상적인 의미에서의 나무는 이 정의에 따른 1나무다.
tree decomposition: 그래프 $G$ 의 트리 분해는 노드가 $G$ 의 꼭지점 집합으로 레이블이 붙여진 나무로, 이러한 집합을 백이라고 한다. 각 꼭지점 $v$ 에 대해 $v$ 를 포함하는 백은 트리의 하위 트리를 유도해야 하며, 각 에지 $uv$ 에 대해 $u$ 와 $v$ 를 모두 포함하는 백이 있어야 한다. 나무 분해의 너비는 가방에서 정점의 최대 개수보다 한 개 작다. $G$ 의 트리 너비는 $G$ 의 트리 분해의 최소 너비다.
treewidth: 그래프 $G$ 의 트리 너비는 $G$ 의 트리 분해의 최소 너비다. 또한 $G$ 의 화음 완성의 clique number, $G$ 의 안식처 순서 또는 $G$ 의 bramble 순서에 따라 정의할 수 있다.
triangle: 그래프에서 길이 3의 주기. 삼각형이 없는 그래프는 삼각형 하위 그래프가 없는 비방향 그래프다.
Turán: 1. 팔 투란; 2. 투란 그래프는 균형잡힌 완전한 다중접합체 그래프다.; 3. 투란의 정리를 보면 투란 그래프는 주어진 순서의 모든 clique-free 그래프 중에서 최대 에지 수를 가지고 있다고 되어 있다.; 4. 투란의 벽돌 공장 문제는 완전한 초당적 그래프의 도면에 최소한의 교차 횟수를 요구한다.

U

undirected: 비방향 그래프는 각 가장자리의 두 끝점이 서로 구별되지 않는 그래프다. 지시 및 혼합도 참조하십시오. 혼합 그래프에서, 비방향 에지는 엔드포인트가 서로 구별되지 않는 에지가 된다.
uniform: 하이퍼그래프는 모든 가장자리에 $k$ 끝점이 있을 때 k-uniform이고, 일부 $k$ 에 대해서는 k-uniform일 때 균일하다. 예를 들어, 일반 그래프는 2-통일 하이퍼그래프와 동일하다.
universal: 1. 범용 그래프는 주어진 그래프 패밀리의 모든 그래프 또는 주어진 크기나 순서의 모든 그래프를 서브그래프로 포함하는 그래프다.; 2. 만능정점(정점 또는 지배정점이라고도 함)은 그래프에서 다른 모든 정점에 인접한 정점이다. 예를 들어 휠 그래프와 연결된 분계점 그래프는 항상 범용 꼭지점을 가진다.; 3. 그래프의 논리에서는 공식으로 보편적으로 정량화된 정점을 그 공식에 대한 보편 정점이라고 할 수 있다.
unweighted graph: 정점과 모서리에 가중치가 할당되지 않은 그래프. 가중 그래프와 반대.
utility graph: 효용 그래프는 완전한 양분 그래프 $K_{3,3}$ $K_{3,3}$ , $K_{3,3}$ ${\$ 의 이름이다 $K_{3,3}$

V

V: 정점 세트를 참조하십시오.
valency: 학위 동의어.
vertex: 꼭지점(플랄 정점)은 그래프를 구성하는 두 가지 기본 단위 중 하나이다. 그래프의 정점은 종종 내부 구조가 없는 원자 개체로 간주된다.
vertex cut
separating set: 제거가 그래프의 연결을 끊는 정점 집합. 한 번 절개하는 것을 관절점 또는 절개정점이라고 한다.
vertex set: 주어진 그래프 $G$ 의 정점 집합이며, $때로는$ V $(G$ )로 표시되기도 한다 $.$
vertices: 꼭지점 참조.
Vizing: 1. 바딤 G. 바이징; 2. 색도지수가 최대도보다 한 개 이상 많다는 Vizing의 정리.; 3. 그래프의 데카르트 산물의 지배적 수에 대한 비징의 추측.
volume: 정점 집합의 각도의 합계.

W

$W$: 문자 W는 휠 그래프와 풍차 그래프의 표기법에 사용된다. 그 표기법은 표준화되어 있지 않다.
Wagner: 1. 클라우스 바그너; 2. 와그너 그래프, 8베르텍스 뫼비우스 사다리.; 3. 그들의 금지된 미성년자들이 평면 그래프를 특징짓는 바그너의 정리.; 4. K-minor-free $5$ 그래프를 특징짓는 바그너의 정리.
walk: 걷기는 정점 순서와 연결되는 유한 또는 무한의 가장자리 시퀀스다. 산책을 사슬이라고도 한다.^[15] 걸음은 첫 번째 정점과 마지막 정점이 구별되면 열리고, 반복되면 닫힌다.
weakly connected: 지시된 그래프는 모든 지시된 가장자리를 비방향 가장자리로 교체하면 연결된(비방향) 그래프가 생성되는 경우 약하게 연결되었다고 불린다.
weight: 그래프의 꼭지점 또는 가장자리에 레이블로 지정된 숫자 값. 서브그래프의 무게는 서브그래프 내의 정점이나 가장자리의 무게의 합이다.
weighted graph: 정점 또는 가장자리의 가중치가 할당된 그래프. 구체적으로는 정점 가중치가 있는 그래프는 정점에 가중치가 있고 가장자리 가중치가 있는 그래프.
well-colored: 색감이 좋은 그래프는 탐욕스러운 색상이 모두 같은 수의 색을 사용하는 그래프다.
well-covered: 잘 덮인 그래프는 최대 독립 집합이 모두 같은 크기인 그래프다.
wheel: 휠 그래프는 단순한 사이클에 범용 꼭지점을 추가함으로써 형성된 그래프다.
width: 1. 타락의 동의어.; 2. 너비로 알려진 다른 그래프 불변성의 경우 대역폭, 분기 너비, 클라이크 너비, 경로 너비 및 트리 너비를 참조하십시오.; 3. 나무 분해나 경로 분해의 폭은 그 가방 중 하나의 최대 크기보다 1이 작으며, 나무 너비와 경로 너비를 정의하는 데 사용할 수 있다.; 4. 지시된 악순환 그래프의 폭은 항균의 최대 카디널리티다.
windmill: 풍차 그래프는 한 개의 정점이 모든 정점에 속하고 다른 모든 정점과 가장자리가 구별되는, 서로 동일한 순서의, 집단 집합의 결합이다.

참고 항목

참조

^ Farber, M.; Hahn, G.; Hell, P.; Miller, D. J. (1986), "Concerning the achromatic number of graphs", Journal of Combinatorial Theory, Series B, 40 (1): 21–39, doi:10.1016/0095-8956(86)90062-6.
^ ^a ^b ^c ^d ^e ^f ^g ^h Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "B.4 Graphs", Introduction to Algorithms (2 ed.), MIT Press and McGraw-Hill, pp. 1080–1084.
^ Grünbaum, B. (1973), "Acyclic colorings of planar graphs", Israel Journal of Mathematics, 14 (4): 390–408, doi:10.1007/BF02764716.
^ 코멘 외 (2001), 페이지 529.
^ Diestel, Reinhard (2017), "1.1 Graphs", Graph Theory, Graduate Texts in Mathematics, vol. 173 (5th ed.), Berlin, New York: Springer-Verlag, p. 3, doi:10.1007/978-3-662-53622-3, ISBN 978-3-662-53621-6.
^ Woodall, D. R. (1973), "The Binding Number of a Graph and its Anderson Number", J. Combin. Theory Ser. B, 15 (3): 225–255, doi:10.1016/0095-8956(73)90038-5
^ Sudakov, Benny; Volec, Jan (2017), "Properly colored and rainbow copies of graphs with few cherries", Journal of Combinatorial Theory, Series B, 122 (1): 391–416, arXiv:1504.06176, doi:10.1016/j.jctb.2016.07.001.
^ "depth". NIST.
^ Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), "Chapter 7: Forbidden Subgraph", Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, pp. 105–121, ISBN 978-0-89871-432-6
^ Mitchem, John (1969), "Hypo-properties in graphs", The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Mich., 1968), Lecture Notes in Mathematics, vol. 110, Springer, pp. 223–230, doi:10.1007/BFb0060121, ISBN 978-3-540-04629-5, MR 0253932.
^ ^a ^b "level". NIST.
^ Harris, John M. (2000). Combinatorics and Graph Theory. New York: Springer-Verlag. p. 5. ISBN 978-0-387-98736-1.
^ Watts, Duncan J.; Strogatz, Steven H. (June 1998). "Collective dynamics of 'small-world' networks". Nature. 393 (6684): 440–442. Bibcode:1998Natur.393..440W. doi:10.1038/30918. PMID 9623998. S2CID 4429113.
^ Bondy, J. A. (1972), "The "graph theory" of the Greek alphabet", Graph theory and applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972; dedicated to the memory of J. W. T. Youngs), Lecture Notes in Mathematics, vol. 303, Springer, pp. 43–54, doi:10.1007/BFb0067356, ISBN 978-3-540-06096-3, MR 0335362
^ "Chain - graph theory". britannica.com. Retrieved 25 March 2018.

[1] Farber, M.; Hahn, G.; Hell, P.; Miller, D. J. (1986), "Concerning the achromatic number of graphs", Journal of Combinatorial Theory, Series B, 40 (1): 21–39, doi:10.1016/0095-8956(86)90062-6.

[clrs-2] ^ ^a ^b ^c ^d ^e ^f ^g ^h Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "B.4 Graphs", Introduction to Algorithms (2 ed.), MIT Press and McGraw-Hill, pp. 1080–1084.

[3] Grünbaum, B. (1973), "Acyclic colorings of planar graphs", Israel Journal of Mathematics, 14 (4): 390–408, doi:10.1007/BF02764716.

[4] 코멘 외 (2001), 페이지 529.

[diestel-5] Diestel, Reinhard (2017), "1.1 Graphs", Graph Theory, Graduate Texts in Mathematics, vol. 173 (5th ed.), Berlin, New York: Springer-Verlag, p. 3, doi:10.1007/978-3-662-53622-3, ISBN 978-3-662-53621-6.

[6] Woodall, D. R. (1973), "The Binding Number of a Graph and its Anderson Number", J. Combin. Theory Ser. B, 15 (3): 225–255, doi:10.1016/0095-8956(73)90038-5

[7] Sudakov, Benny; Volec, Jan (2017), "Properly colored and rainbow copies of graphs with few cherries", Journal of Combinatorial Theory, Series B, 122 (1): 391–416, arXiv:1504.06176, doi:10.1016/j.jctb.2016.07.001.

[8] "depth". NIST.

[9] Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), "Chapter 7: Forbidden Subgraph", Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, pp. 105–121, ISBN 978-0-89871-432-6

[10] Mitchem, John (1969), "Hypo-properties in graphs", The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Mich., 1968), Lecture Notes in Mathematics, vol. 110, Springer, pp. 223–230, doi:10.1007/BFb0060121, ISBN 978-3-540-04629-5, MR 0253932.

[NIST_Level-11] "level". NIST.

[12] Harris, John M. (2000). Combinatorics and Graph Theory. New York: Springer-Verlag. p. 5. ISBN 978-0-387-98736-1.

[13] Watts, Duncan J.; Strogatz, Steven H. (June 1998). "Collective dynamics of 'small-world' networks". Nature. 393 (6684): 440–442. Bibcode:1998Natur.393..440W. doi:10.1038/30918. PMID 9623998. S2CID 4429113.

[14] Bondy, J. A. (1972), "The "graph theory" of the Greek alphabet", Graph theory and applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972; dedicated to the memory of J. W. T. Youngs), Lecture Notes in Mathematics, vol. 303, Springer, pp. 43–54, doi:10.1007/BFb0067356, ISBN 978-3-540-06096-3, MR 0335362

[15] "Chain - graph theory". britannica.com. Retrieved 25 March 2018.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[14]

[15]

Search

그래프 이론 용어집

네임스페이스

더

기호

A

B

C

D

E

F

G

H

I

K

L

M

N

O

P

Q

R

S

T

U

V

W

참고 항목

참조