Eis a lista de termos técnicos, notação e pessoas no livro Exercícios de Teoria dos Grafos. Para cada termo técnico, o índice dá a página do livro onde o termo é definido.
⌊x⌋ ... 10
⌊x⌋ ... 38
⌈x⌉ ... 76
V(2) ... 8
Adj ... 17
VG ... 8
EG ... 8
n(G) ... 8
m(G) ... 8
c(G) ... 39
d(v) ... 17
d(X) ... 29
... 8
Kn ... 8
Kp,q ... 15
Qk ... 12
L(G) ... 14
N(v) ... 17
N(X) ... 30
X ⊂ Y ... 26
Y ⊃ X ... 26
A ⊕ B ... 30
G ⊆ H ... 26
G ∪ H ... 24
G ∩ H ... 24
G[X] ... 26
G ≅ H ... 61
G(n) ... 59
G−v ... 26
G−X ... 26
G−e ... 26
G−A ... 26
α(G) ... 73
α'(G) ... 97
β(G) ... 83
γ(G, S) ... 110
δ(G) ... 17
δ(X) ... 29
Δ(G) ... 17
κ(G) ... 133
κ'(G) ... 129
μ(G) ... 17
o(G) ... 109
χ(G) ... 85
χ'(G) ... 113
ω(G) ... 79
∂(X) ... 29
∇(X) ... 29
A
α(G) ... 73
α'(G) ... 97
abrangente (subgrafo) ... 26
acíclico ... 119
adjacent ... 8
adjacentes
arestas ... 14, 97
vértices ... 8
alcanos ... 9
aleatório ... 59
algoritmo
de aproximação ... 84, 101
de Kruskal ... 121
de Prim ... 121
fluxo máximo e corte mínimo ... 128
guloso ... 75, 88, 92, 115
húngaro ... 105
alternating ... 98
Appel ... 93
aresta ... 8
de corte ... 42
aresta-biconexo ... 44, 129
aresta-conexidade ... 129
aresta-k-conexo ... 129
arestas
adjacentes ... 14, 97
múltiplas ... 8, 55
paralelas ... 8, 55
articulação ... 45
articulation ... 45
árvore ... 47
abrangente ... 119
das distâncias ... 124
geradora ... 119
augmenting path ... 98
auto-complementar ... 64
B
β(G) ... 83
Barnette ... 140
Berge ... 95
BFS ... 124
bicoloração ... 69
bicolorável ... 69
biconexo ... 45, 133
aresta-biconexo ... 44
biconnected ... 45
bipartição
de conjunto ... 69
de grafo ... 15
bipartido ... 15
completo ... 15
bipartite ... 15
bishop ... 11
bispo ... 11
Bollobás ... 5
breadth-first search ... 124
bridge ... 42
buraco ímpar ... 95
busca em largura ... 124
C
c(G) ... 39
caixeiro viajante ... 139
caminho ... 21
alternante ... 98
de aumento ... 98
hamiltoniano ... 135
ímpar ... 71
ímpar mínimo ... 126
maximal ... 32
máximo ... 32, 135
mínimo ... 123
par ... 71
par mínimo ... 126
carteiro chinês ... 144
Catlin ... 87
cavalo ... 11
centro ... 125
certificado ... 71, 90, 101, 110, 128, 142
chinese postman ... 144
chromatic
index ... 113
number ... 85
Chudnovsky ... 95
Chvátal ... 138
ciclo ... 35, 143
euleriano ... 143
cintura ... 123
ímpar ... 125
par ... 125
circuit cover ... 141
circuit decomposition ... 141
circuit double cover ... 146
circuito ... 21
hamiltoniano ... 135
ímpar ... 69, 71
ímpar mínimo ... 125
máximo ... 135
mínimo ... 123
par ... 71
par mínimo ... 125
circunferência ... 135
clique ... 79
clique cover ... 86
clique number ... 79
closed ... 35, 143
cobertura ... 83
dupla por circuitos ... 146
por arestas ... 111
por circuitos ... 141
por cliques ... 86
por vértices ... 83
coboundary ... 29
coleção ... 59
colorable ... 85
k-coloração ... 85
coloração
de arestas ... 113
de vértices ... 85
mínima ... 85, 113
colorável ... 85
k-colorável ... 85
comparabilidade ... 14
complemento ... 8
completo ... 8
componente ... 39
ímpar ... 109
comprimento
de caminho ... 21
de circuito ... 21
de passeio ... 34, 143
de trilha ... 35
conector ... 119
conexidade ... 129, 133
conexo ... 36
k-conexo ... 133
conjectura
Barnette ... 140
Berge ... 95
Chvátal ... 138
cobertura dupla por circuitos ... 146
Hadwiger ... 94
conjunto
acíclico ... 119
completo ... 79
estável ... 73
independente ... 73
connected ... 36
corte ... 29
trivial ... 29
cubo ... 12
k-cubo ... 12
cut ... 29
cut edge ... 42
cut vertex ... 45
cycle ... 35, 143
D
DD ... 6
δ(G) ... 17
δ(X) ... 29
Δ(G) ... 17
d(v) ... 17
d(X) ... 29
∂(X) ... 29
dama ... 10
decomposição
em circuitos ... 141
degree ... 17
desigualdade triangular ... 124
diâmetro ... 126
diferença simétrica ... 30, 99
Dirac ... 134, 138, 149
disjuntos internamente ... 45
dist( ) ... 123
distância ... 123
dual de mapa plano ... 55
E
E ... 6
o E ... 6
! E ... 6
!! E ... 6
* E ... 6
*! E ... 6
*o E ... 6
> E ... 6
E ♥ ... 6
EG ... 8
edge ... 8
edge cover ... 111
edge-biconnected ... 44
Edmonds ... 111
Egerváry ... 111
emparelhamento ... 97
de peso máximo ... 111
perfeito ... 97
Erdös ... 68, 117
estável ... 73
estrela ... 15
Euler ... 56, 143
euleriana ... 143
excentricidade ... 125
exoplanar ... 58
extremos de caminho ... 21
F
face ... 54
face ... 54
fechado (passeio, trilha) ... 35, 143
filho de vértice ... 47
floresta ... 47
flow ... 127
fluxo ... 127
internamente disjunto ... 131
fluxo máximo ... 127
folha ... 47
forest ... 47
fórmula de Euler ... 56
franja ... 29
fronteira de face ... 54
G
γ(G, S) ... 110
G(n) ... 59
Gallai ... 68, 91, 111
gerador (subgrafo) ... 26
girth ... 123
grade ... 10
gráfica (sequência) ... 67
grafo ... 8
-linha ... 14
acíclico ... 47
aleatório ... 59
aresta-biconexo ... 44, 129
bicolorável ... 69
biconexo ... 45, 133
bipartido ... 15
bipartido completo ... 15
k-colorável ... 85
complementar ... 8
completo ... 8
cúbico ... 17
da dama ... 10
da torre ... 11
das arestas ... 14
das faces ... 55
das palavras ... 12
de Catlin ... 87
de comparabilidade ... 14
de Heawood ... 33, 125
de intervalos ... 14
de Kneser ... 12
de mapa plano ... 53
de matriz simétrica ... 13
de Petersen ... 12
de Turán ... 77
do bispo ... 11
do cavalo ... 11
do rei ... 12
dos estados ... 13
dual ... 55
exoplanar ... 58
grade ... 10
lineal ... 14
perfeito ... 95
planar ... 25, 54
plano ... 53
regular ... 17
simples ... 8
vazio ... 8
grafos disjuntos ... 24
graph ... 8
graph design ... 67
grau
de conjunto de vértices... 29
de face ... 54
de vértice ... 17
máximo ... 17
médio ... 17
mínimo ... 17
greedy ... 75, 88
grid ... 10
guloso ... 75
H
Hadwiger ... 94
Hajós ... 94
Haken ... 93
Hall ... 106
Hamilton ... 135
hamiltoniano ... 135
Heawood ... 33, 125
heurística
da troca de cores ... 116
hexágono ... 21
hidrocarbonetos ... 9
I
incide ... 8
independence number ... 73
independent ... 73
índice de estabilidade ... 73
indução ... 26, 136
internamente disjunto ... 131
interseção de grafos ... 24
intervalos ... 14
isolado (vértice) ... 17
isolador ... 31
isomorfismo ... 61
isomorphism ... 61
isthmus ... 42
istmo ... 42
K
Kn ... 8
Kp,q ... 15
n ... 8
κ(G) ... 133
κ'(G) ... 129
king ... 12
Kirkman ... 135
Kneser ... 12
knight ... 11
König ... 104, 116
Kruskal ... 121
Kuratowski ... 148
L
L(G) ... 14
laço ... 8, 55
leaf ... 47
liga u a v ... 21
ligado ... 36
line graph ... 14
lineal (grafo) ... 14
linhas (de mapa plano) ... 53
loop ... 8, 55
Lovász ... 5, 13, 95
M
m(G) ... 8
μ(G) ... 17
máinor ... 50
mapa plano ... 53
matching ... 97
maximum weight ... 111
matriz
de adjacências ... 9
de incidências ... 9
maximal ... 73, 97
maximal vs máximo ... 32, 73, 97, 119
máximo ... 27, 73, 97
Menger ... 128, 132
menor ... 50
menor topológico ... 50
minimal vs mínimo ... 119
minor ... 50
multiple edges ... 8, 55
N
n(G) ... 8
N(v) ... 17
N(X) ... 30
não ordenado ... 8
neighbor ... 8
neighborhood ... 17
NP-completo ... 5
NP-difícil ... 5
número cromático ... 83
número de cores ... 85, 113
O
o(G) ... 109
ω(G) ... 79
odd component ... 109
odd hole ... 95
ordem parcial ... 14
origem de passeio ... 34
outerplanar ... 58
P
pai de vértice ... 47
palavras ... 12
par não ordenado ... 8
parallel edges ... 8, 55
paridade ... 71
partição ... 15
passeio ... 34, 143
de v a w ... 34, 143
fechado ... 35
simples ... 35
pentágono ... 21
perfect
elimination scheme ... 90
graph ... 95
matching ... 97
perfeito
emparelhamento ... 97
grafo ... 95
periplanar ... 58
permutação ... 21, 47
peso de aresta ... 111, 121
Petersen ... 12
planar ... 25, 54, 147
ponta de aresta ... 8
ponte ... 42
pontos (de mapa plano) ... 53
Prim ... 121
problema
do caixeiro viajante ... 139
do carteiro chinês ... 144
Q
Qk ... 12
quadrado ... 21
quase todo ... 59
queen ... 11
R
raiz de árvore ... 47
random ... 13
regular ... 17
rei ... 12
Robertson ... 93, 95
roda ... 24
rook ... 11
Roy ... 91
S
separa ... 34, 127, 131
separador ... 131
sequência gráfica ... 67
Seymour ... 93, 95, 146
slither ... 100
spanning ... 26, 119
stability number ... 73
stable ... 73
star ... 15
subcontração ... 50
subdivisão ... 51
subgrafo ... 26
abrangente ... 26
gerador ... 26
induzido ... 26
maximal ... 39
próprio ... 26
subpartição ... 50
suporte de mapa plano ... 54
Szekeres ... 146
T
tabuleiro ... 11
teorema das
Quatro Cores ... 93
teorema de
Berge ... 100
Brooks ... 89
Dirac ... 134, 138
Erdös e Gallai ... 68
Euler ... 142
Gallai e Roy ... 91
Hall ... 106
Havel e Hakimi ... 68
König ... 116
König–Egerváry ... 104
Kuratowski ... 148
Menger ... 128, 132
Turán ... 77
Tutte ... 109, 140
Tutte–Berge ... 110
Veblen ... 142
Vizing ... 117
Wagner ... 148
término de passeio ... 34
Thomas ... 93, 95
topological minor ... 50
torre ... 11
trail ... 35, 143
traveling salesman ... 139
tree ... 47
triângulo ... 21
trilha ... 35, 143
euleriana ... 143
fechada ... 143
TSP ... 139
Turán ... 77
Tutte ... 109, 140
U
união de grafos ... 24
usa k cores ... 85
V
VG ... 8
vai de v a w ... 32
vazio ... 8
vertex cover ... 83
vértice ... 8
de corte ... 45
interno ... 21, 131
isolado ... 17
saturado ... 97
vértices
brancos ... 15
pretos ... 15
vértices adjacentes ... 8
vizinho ... 8
W
Wagner ... 148
walk ... 34, 143
wheel ... 24
X
χ(G) ... 85
χ'(G) ... 113
Y
Younger ... 5