Teoria dos Grafos

Description

Conceitos para a construção de grafos.
Mateus Ferro
Flashcards by Mateus Ferro, updated more than 1 year ago More Less
Natalie Bravo
Created by Natalie Bravo almost 6 years ago
Mateus Ferro
Copied by Mateus Ferro almost 4 years ago
10
1

Resource summary

Question Answer
Grafo G=(V,E) Estrutura matemática que consiste em 2 conjuntos finitos. 1º. conjunto dos vértices (V) 2º. conjunto das arestas (E)
O que é uma extremidade? Cada aresta consiste de um par não ordenado de elementos de V. Cada elemento de uma aresta é chamado extremidade.
O 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
Vizinhança Aberta de v N(v) Conjunto de vértices vizinhos de v
Vizinhança Fechada de v N[v] N[v] = N(v) U {v}
Aresta Própria É aquela que une dois vértices distintos.
Self-loop ou Laço É a aresta que liga um vértice a ele mesmo.
Multiaresta Coleção de 2 ou mais arestas que têm as mesmas extremidades.
Grafos Simples É aquele que NÃO possui multiarestas e nem self-loops
Multigrafo É aquele que possui pelo menos uma multiaresta e NÃO possui self-loop
Grafo Geral (pseudografo) É aquele que pode apresentar self-loop e/ou multiaresta
Grafo Nulo É um grafo
Grafo Trivial É um grafo com 1 único vértice e 0 arestas
Aresta Direcionada (arco) É uma aresta que parece uma seta.
Muti-Arco É um conjunto de dois ou mais arcos que têm a mesma cabeça e calda.
Digrafo (grafo direcionado) É um grafo que possui todas as arestas direcionadas.
Digrafo Simples É aquele que NÃO possui multi-arcos e nem self-loop.
Grafo Misto Apresenta arestas e arcos.
Grafo Subjacente (Grafo Base) É um grafo obtido a partir da substituição dos arcos de um digrafo por arestas.
Vértices Adjacentes u e v são adjacentes se existe pelo menos uma aresta os ligando.
Arestas Adjacentes São aquelas que possuem pelo menos uma extremidade em comum.
v é incidente em e & e é incidente em v O vértice v é extremidade da aresta e
Valência de v (grau) d(v) Nº de arestas próprias incidentes em v + 2*nº de self-loops
δ e Δ δ = menor grau de um grafo Δ = maior grau de um grafo
Sequência de Grau de G Sequência formada pela disposição crescentes dos graus dos vértices de G
Um grafo simples não trivial G deve ter... ...pelo menos um par de vértices com o mesmo grau.
A soma dos graus de um vértice... ...é o dobro do número de arestas.
Em um grafo, existe um número par de... ...vértices de grau ímpar
A sequência de grau de um grafo é finita e... ...decrescente de inteiros não negativos cuja soma é par
Toda sequência finita decrescente de inteiros não negativos que a soma é par... ...é sequência de grau de algum grafo.
Grau de Entrada d+(v) Nº de arcos direcionados para v
Grau de Saída d-(v) Nº de arcos cuja origem é v
Em 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
A ORDEM de um grafo G é... |V| = n (nº de vértices de G)
Cobertura 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
Subconjunto independente de G... É um subconjunto de vértices de G que não possuem arestas em comum.
Conjunto 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.
Emparelhamento ou matching... É um subconjunto de arestas de G que NÃO são mutuamente adjacentes.
Kn Grafo completo de ordem n (n º de vértices)
Um grafo Kn tem o nº de arestas = ... nº arestas = n*(n-1)/2
K p,q É um gafo bipartido completo.
Grafo REGULAR... É um grafo em que todos os vértices tem o mesmo grau.
Grafo K-regular... Grafo regular cujo os nós tem grau K.
Grafo de Pertson... Grafo 3-regular:
Grafo caminho ou Grafo linear (Pn) É um grafo em que o |V| = |A| + 1
Grafo círculo (Cn) É um grafo com um único vértice e um self-loop OU um grafo simples com |V| = |A|
Caminho ou passeio É uma sequência alternada de vértices e arestas de um nó Vo até Vk.
Caminho Simples Um caminho que não repete vértices.
Trilha Um caminho que não repete arestas.
Comprimento de um caminho Nº de arestas da sequência que compoẽ o caminho.
Caminho trivial Apresenta comprimento 0, ou seja, possui um vértice e nenhuma aresta.
Ciclo (caminho fechado) Caminho não trivial que começa e termina no mesmo vértice.
Circuito (caminho direcionado fechado) É um caminho direcionado não trivial que começa e termina no mesmo vértice.
Concatenação de dois caminhos Sendo W1 ={ a, b} o caminho 1 e W2 ={x, y} o caminho 2: W1 o W2 = {a, b, x, y}
Distâ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
Excentricidade de um vértice exc(v) É a distância de v ao seu vértice mais distante
Diâmetro de G diam(G) É o maior valor de excentricidade dentre todos os vértices de V.
Raio de G rad(G) É o menor valor de excentricidade dentre todos os vértices de G.
Um vértice de G é CENTRAL se... ...a sua excentricidade é igual ao raio de G, ou seja, se exc(v) = rad(G).
Grafo Conexo É aquele que possui um caminho entre quaisquer pares de vértices.
Grafo fortemente conexo Se para qualquer par de vértice u e v existe um caminho direcionado de u para v e vice versa.
Componente conexa Subconjunto maximal de vértices em que para qualquer vértice v e u existe um caminho.
Ciclo hamiltoniano um ciclo que inclui todos os vértices de um grafo.
Grafo hamiltoniano Grafo que apresenta um ciclo hamiltoniano.
Um grafo G é bipartido se e somente se... ...não apresenta ciclo de tamanho ímpar.
Trilha euclidiana É aquela que contém todas as arestas de G.
tour(ciclo) euclidiano É uma trilha euclidiana fechada.
Grafo euclidiano É aquele que possui um ciclo euclidiano.
Circunferência de um grafo É o tamanho do maior ciclo de G.
Árvore É um grafo que não apresenta ciclos.
Isomorfismo de grafo Um 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.
Seja G e H grafos isomorfos e u ∈ Vg, então... d(v) = d(f(v))
Seja G e H grafos isomorfos, então... ... G e H tem a mesma sequência de grau.
Seja 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.
Um subgrafo H de um grafo conexo G é dito GERADOR de G se... Vh = Vg e for conexo
Árvore de cobertura É um subgrafo gerador de G conexo que não apresenta ciclos.
Floresta (grafo acíclico)
Show full summary Hide full summary

Similar

História da informática
Renato Costa
Memória Computacional
Filipe Gabriel
QUESTIONÁRIO DE INFORMÁTICA: SISTEMAS OPERACIONAIS
anapaulabrasilam
Organização e Arquitetura de Computador
Rodrigo Gomes
ARQUITETURA DE COMPUTADORES
wesley.silva.ads
Ciência da Computação
charlinston.binko
LINGUAGEM DE PROGRAMAÇÃO I
ailtonmidias
Lógica de Programação- Dados
Gabriela Alves
Servidores de Web e de Aplicação
Raphael Luiz Fonseca
Fundamentos Matemáticos paraComputação (Motivação)
Francisco Sávio de Almeida Miranda
Dijkstra
Rodrigo Amaral