Índice remissivo

O índice dá a página do livro onde cada termo técnico é definido.  (Esta versão do índice pode estar ligeiramente desatualizada. Veja a versão atualizada nas últimas páginas do livro.)

x⌋ ... 10, 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

G ... 8

Kn ... 8

Kp,q ... 15

Qk ... 12

L(G) ... 14

N(v) ... 17

N(X) ... 30

XY ... 26

YX ... 26

AB ... 30

GH ... 26

GH ... 24

GH ... 24

G[X] ... 26

GH ... 61

G(n) ... 59

Gv ... 26

GX ... 26

Ge ... 26

GA ... 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

 

α(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

 

β(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(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

 

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 ... 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

 

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, 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

 

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

 

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

 

Kn ... 8

Kp,q ... 15

Kn ... 8

κ(G) ... 133

κ'(G) ... 129

king ... 12

Kirkman ... 135

Kneser ... 12

knight ... 11

König ... 104, 116

Kruskal ... 121

Kuratowski ... 148

 

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(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(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(G) ... 109

ω(G) ... 79

odd component ... 109

odd hole ... 95

ordem parcial ... 14

origem de passeio ... 34

outerplanar ... 58

 

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

 

Qk ... 12

quadrado ... 21

quase todo ... 59

queen ... 11

 

raiz de árvore ... 47

random ... 13

regular ... 17

rei ... 12

Robertson ... 93, 95

roda ... 24

rook ... 11

Roy ... 91

 

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

 

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

 

união de grafos ... 24

usa k cores ... 85

 

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

 

Wagner ... 148

walk ... 34, 143

wheel ... 24

 

χ(G) ... 85

χ'(G) ... 113

 


http://www.ime.usp.br/~pf/grafos-exercicios/
Last modified: Wed Sep 27 13:14:12 BRT 2017
Paulo Feofiloff
DCC  |  IME  |  USP