Grafos Flashcards
(28 cards)
Circuito orientado
Um circuito orientado num grafo orientado é um
caminho orientado que começa e termina no mesmo nodo.
Multigrafo
Se um grafo admite mais do que uma
aresta entre dois vértices diz-se multigrafo
Subgrafo Gerador
H é subgrafo gerador de G se os vértices de H forem iguais aos vértices de G
Caminho orientado
Um caminho orientado num grafo orientado é uma
sucessão de arcos e1 e2 …….ek tal que o primeiro elemento do par ei coincide com o segundo elemento
de ei-1 e o segundo elemento de ei
com o primeiro elemento de ei+1
Caminho simples
Um caminho simples é um caminho que
não passa duas vezes pelo mesmo nodo.
Distancia
A distância d(v, w) entre dois nodos v e w de um
grafo define-se como a longitude do caminho “mais
curto” entre ambos.
Subgrafo induzido por
Pode ser os subgrafo vértice-induzido ou aresta-induzido
Circuito
Um circuito é um caminho que começa e
termina no mesmo nodo.
Subgrafos
Um grado H é um subgrafo do grafo G se os vértices de H estiverem incluídos nos vértices de G e as arestas de H estiverem incluídas nas arestas de G
Listas de Adjacência
Para cada um dos vértices por ordem:
[] com vértices com os quais estão diretamente conectados
Grafo
Um grafo G = (V,X) é um par de conjuntos,
onde V é um conjunto de vértices, pontos ou
nodos e X é um subconjunto do conjunto de
pares não ordenados de elementos distintos
de V .
Os elementos de X designam-se por arcos ou
arestas.
Cadeia
Uma Cadeia é um caminho orientado, onde pelo menos
um dos arcos é percorrido em sentido contrário.
Circuito Simples
Um circuito simples é um circuito de 3 ou
mais nodos que não passa duas vezes pelo
mesmo nodo.
Grau de saida
O grau de saída dout(v) de um nodo de um grafo
orientado é a quantidade de arcos que “saem” de v, ou
seja, a quantidade de arcos que têm v como seu
primeiro elemento
Grau de entrada
O grau de entrada din(v) de um nodo de um grafo
orientado é a quantidade de arcos que “chegam” a v, ou
seja, a quantidade de arcos que têm v como o seu
segundo elemento.
Grafo regular
Grafo regular. Todos os vértices do grafo
tem o mesmo grau.
Matriz de Incidência nodo-arco
(grafo orientado)
Matriz em que:
colunas -> arcos
linhas -> vértices
1 se o vértice for o ponto de partida do arco
-1 se o vértice for o ponto de chegada do arco
0 se o arco não tiver os vértices
Grau de um vértice
O grau de um nodo v é a quantidade de
arcos incidentes em v.
* Notação: d(v) = grau de v
* Teorema: A soma dos graus dos vértices de
um grafo é 2 vezes o número de arcos, ou
seja:
Grafo Orientado
Se os arcos têm um sentido a ser
respeitado, o grafo diz-se orientado ou digrafo
Grafo completo
Um grafo diz-se completo se todos os
vértices são adjacentes entre si.
Notação: Kn
grafo completo de n vértices.
Longitude
A longitude de um caminho é a quantidade de arcos
que formam o caminho.
Matriz de adjacência
Matriz em que:
colunas -> vértices
linhas -> vértices
1 se houver arco entre vértices
0 se não houver arco entre vértices
Custo
O custo c(v, w) de um caminho é a soma do custo de
travessia de cada arco que formam o caminho.
Vértices adjacentes
vértices adjacentes porque existe um arco de união
