Flashcards

Teoria dos Grafos

Natalie Bravo Portuguese 77 cards

Cards in this deck (77)

1Grafo G=(V,E)Estrutura matemática que consiste em 2 conjuntos finitos.
1º. conjunto dos vértices (V)
2º. conjunto das arestas (E)
2O que é uma extremidade?Cada aresta consiste de um
par não ordenado de elementos de V.
Cada elemento de uma aresta é chamado extremidade.
3O que significa uma aresta e = (u,v)Os vértices u, v estão ligados pela aresta e.
u é vizinho de v e vice-versa
4Vizinhança Aberta de v N(v)Conjunto de vértices vizinhos de v
5Vizinhança Fechada de v N[v]N[v] = N(v) U {v}
6Aresta PrópriaÉ aquela que une dois vértices distintos.
7Self-loop ou LaçoÉ a aresta que liga um vértice a ele mesmo.
8MultiarestaColeção de 2 ou mais arestas que têm as mesmas extremidades.
9Grafos SimplesÉ aquele que NÃO possui multiarestas e nem self-loops
10MultigrafoÉ aquele que possui pelo menos uma multiaresta e NÃO possui self-loop
11Grafo Geral (pseudografo)É aquele que pode apresentar self-loop e/ou multiaresta
12Grafo NuloÉ um grafo
13Grafo TrivialÉ um grafo com 1 único vértice e 0 arestas
14Aresta Direcionada (arco)É uma aresta que parece uma seta.
15Muti-ArcoÉ um conjunto de dois ou mais arcos que têm a mesma cabeça e calda.
16Digrafo (grafo direcionado)É um grafo que possui todas as arestas direcionadas.
17Digrafo SimplesÉ aquele que NÃO possui multi-arcos e nem self-loop.
18Grafo MistoApresenta arestas e arcos.
19Grafo Subjacente (Grafo Base)É um grafo obtido a partir da substituição dos arcos de um digrafo por arestas.
20Vértices Adjacentesu e v são adjacentes se existe pelo menos uma aresta os ligando.
21Arestas AdjacentesSão aquelas que possuem pelo menos uma extremidade em comum.
22v é incidente em e & e é incidente em vO vértice v é extremidade da aresta e
23Valência de v (grau) d(v)Nº de arestas próprias incidentes em v + 2*nº de self-loops
24δ e Δδ = menor grau de um grafo
Δ = maior grau de um grafo
25Sequência de Grau de GSequência formada pela disposição crescentes dos graus dos vértices de G
26Um grafo simples não trivial G deve ter......pelo menos um par de vértices com o mesmo grau.
27A soma dos graus de um vértice......é o dobro do número de arestas.
28Em um grafo, existe um número par de......vértices de grau ímpar
29A sequência de grau de um grafo é finita e......decrescente de inteiros não negativos cuja soma é par
30Toda sequência finita decrescente de inteiros não negativos que a soma é par......é sequência de grau de algum grafo.
31Grau de Entrada d+(v)Nº de arcos direcionados para v
32Grau de Saída d-(v)Nº de arcos cuja origem é v
33Em um digrafo G, a soma dos graus de entrada e a soma dos graus de saída são ambas......iguais ao número de arcos de G
34A ORDEM de um grafo G é...|V| = n
(nº de vértices de G)
35Cobertura de vértices de G...é um conjunto de vértices de G em que todas as arestas de G possui pelo menos uma ponta nesse conjunto
36Subconjunto independente de G...É um subconjunto de vértices de G que não possuem arestas em comum.
37Conjunto Dominante de G...É um subconjunto de vértices tal que todo vértice do grafo ou está no conjunto ou é adjacente a um vértice do conjunto.
38Emparelhamento ou matching...É um subconjunto de arestas de G que NÃO são mutuamente adjacentes.
39KnGrafo completo de ordem n (n º de vértices)
40Um grafo Kn tem o nº de arestas = ...nº arestas = n*(n-1)/2
41K p,qÉ um gafo bipartido completo.
42Grafo REGULAR...É um grafo em que todos os vértices tem o mesmo grau.
43Grafo K-regular...Grafo regular cujo os nós tem grau K.
44Grafo de Pertson...Grafo 3-regular:
45Grafo caminho ou Grafo linear (Pn)É um grafo em que o |V| = |A| + 1
46Grafo círculo (Cn)É um grafo com um único vértice e um self-loop OU um grafo simples com
|V| = |A|
47Caminho ou passeioÉ uma sequência alternada de vértices e arestas de um nó Vo até Vk.
48Caminho SimplesUm caminho que não repete vértices.
49TrilhaUm caminho que não repete arestas.
50Comprimento de um caminhoNº de arestas da sequência que compoẽ o caminho.
51Caminho trivialApresenta comprimento 0, ou seja, possui um vértice e nenhuma aresta.
52Ciclo (caminho fechado)Caminho não trivial que começa e termina no mesmo vértice.
53Circuito (caminho direcionado fechado)É um caminho direcionado não trivial que começa e termina no mesmo vértice.
54Concatenação de dois caminhosSendo W1 ={ a, b} o caminho 1 e W2 ={x, y} o caminho 2:
W1 o W2 = {a, b, x, y}
55Distância d(s, t)A distância de um vértice s a um vértice t é o comprimento do menor caminho s-t, se existir caminho, caso contrário d(s, t) = infinito
56Excentricidade de um vértice exc(v)É a distância de v ao seu vértice mais distante
57Diâmetro de G diam(G)É o maior valor de excentricidade dentre
todos os vértices de V.
58Raio de G rad(G)É o menor valor de excentricidade dentre
todos os vértices de G.
59Um vértice de G é CENTRAL se......a sua excentricidade é igual ao raio de
G, ou seja, se exc(v) = rad(G).
60Grafo ConexoÉ aquele que possui um caminho entre quaisquer pares de vértices.
61Grafo fortemente conexoSe para qualquer par de vértice u e v existe um caminho direcionado de u para v e vice versa.
62Componente conexaSubconjunto maximal de vértices em que para qualquer vértice v e u existe um caminho.
63Ciclo hamiltonianoum ciclo que inclui todos os vértices de um grafo.
64Grafo hamiltonianoGrafo que apresenta um ciclo hamiltoniano.
65Um grafo G é bipartido se e somente se......não apresenta ciclo de tamanho ímpar.
66Trilha euclidianaÉ aquela que contém todas as arestas de G.
67tour(ciclo) euclidianoÉ uma trilha euclidiana fechada.
68Grafo euclidianoÉ aquele que possui um ciclo euclidiano.
69Circunferência de um grafoÉ o tamanho do maior ciclo de G.
70ÁrvoreÉ um grafo que não apresenta ciclos.
71Isomorfismo de grafoUm isomorfismo dos grafos G e H é uma bijeção entre os conjuntos de vértices de G e H de tal forma que quaisquer dois vértices u e v de G são adjacentes em G se e somente se ƒ(u) e ƒ(v) são adjacentes em H.
72Seja G e H grafos isomorfos e u ∈ Vg, então...d(v) = d(f(v))
73Seja G e H grafos isomorfos, então...... G e H tem a mesma sequência de grau.
74Seja f : G --> H um isomorfismo e e ∈ Eg, então......as extremidades de f(e) têm
os mesmos valores de grau das extremidades de e.
75Um subgrafo H de um grafo conexo G é dito GERADOR de G se...Vh = Vg e for conexo
76Árvore de coberturaÉ um subgrafo gerador de G conexo que não apresenta ciclos.
77Floresta (grafo acíclico)