Teoria dos Grafos

Question 1

Grafo Bipartido?

Answer 1

Um grafo G, com pelo menos uma aresta, diz-se bipartido se
existe uma partição do seu conjunto de vértices em X e Y tal
que não existem arestas entre qualquer par de vértices de X
nem entre qualquer par de vértices de Y (ou seja, cada aresta
de G tem um extremo em X e outro em Y). Esta partição (X, Y)
do conjunto dos vértices de G designa-se por bipartição dos
vértices e, neste caso, G denota-se pelo terno (X, Y, E) onde
E = E(G).

Dividir os vertices em dois conjuntos distintos. So ha uma aresta do conjunto X para Y

Question 2

Circuito/Ciclo nos Grafos Bipartidos?

Answer 2

Têm de ter um comprimento par.

Um grafo sem ciclos de comprimento impar (ou seja, com ciclos de comprimento par) é bipartido.

Sendo um ciclo o vertice inicial e o mesmo que o vertice final.

Porque num grafo bipartido não pode haver ligações dentro da partição X e Y.

Question 3

Uma arvore tem ciclos?

Answer 3

Nao, as arvores nao tem ciclos, logo podem ser consideradas grafos bipartidos no caso de terem 2 vertices.

Question 4

Grafo Conexo?

Answer 4

Um grafo diz-se conexo se entre cada par de vértices existe um caminho que os une. Caso contrário, o grafo diz-se não conexo (ou desconexo).

Question 5

Ponte?

Propriedades?

Answer 5

Uma aresta que torna o vertice conexo. Se a retirarmos o grafo deixa de ser conexo.

Uma aresta de um grafo G diz-se uma ponte ou uma aresta de corte se cc(G − e) > cc(G).

Se retirarmos esta aresta do grafo o numero de componentes conexas aumenta.

Propriedades: Se uv for ponte

1. cc(G - uv) = cc(G) + 1
2. Os vertices u e v nao sao conexos em G - uv
3. A aresta uv nao esta contida em nenhum circuito de G.

Question 6

Arvore Abrangente?

Answer 6

Um subgrafo arvore que contem todos os vertices de G.

Um grafo conexo ciclico com 5 vertices, tem 5 arvores abrangentes.

Todo o grafo conexo admite uma arvore abrangente.

Question 7

Ao retirarmos uma ponte de um grafo conexo o numero total de arvores abrangente sera dado como?

Answer 7

Multiplicando o numero de arvores abrangentes de cada um dos grafos que ficaram separados.

Isto e:

T(G-e)=T(G1)*T(G2)

Question 8

Teorema de Cayley?

Answer 8

Numero de arvores abrangentes de um grafo completo com n vertices:

T(Kn)= n^n-2, n>=2

Question 9

Kruskal? Para que serve?

Como comeca?

Answer 9

Ordenar as arestas por custo minimo.

Organizar a tabela em iteracao, current aresta, grafo (desenho) e custo total.

Comecar por escolher na primeira iteracao a aresta com menor custo e preencher os espacos.

Nas proximas iteracoes so adicionamos arestas que nao formem ciclos.

Question 10

Caminho mais curto/Algoritmo de Djiskstra/Caminho de custo minimo?

Como comeca?

Como marcamos os pontos inacessiveis?

Como sera dado o caminho mais curto?

Answer 10

Organizar uma tabela com todos os vertices e assinalar onde queremos comecar e acabar.

Comecar na iteracao 0 e marcar as distancias do ponto em que estamos para aqueles que podemos ir.

Todos os pontos inacessiveis pelo ponto em que estamos tem distancia infinita.

Analisamos todas as hipoteses de escolha de caminho e escolhemos aquele que tem menos custo.

Esse vertice fica agora permanente e repetimos ate chegarmos onde queremos. Ou seja o vertice ja nao pode ser escolhido.

O caminho mais curto sera de cada linha o vertice que tiver menos custo de baixo para cima.

Question 11

Como se representa o numero de vertices?

Answer 11

V(G)

Question 12

Como se representa o numero de arestas?

Answer 12

E(G)

Question 13

O que e a funcao de incidencia?

Answer 13

E uma funcao que descreve a quais vertices liga uma dada aresta.

Ex: Ψg(e1)=1,4 Quer dizer que a aresta e1 liga o vertice 1 e 4

Question 14

Se houver um lacete num grafo como sera a funcao incidencia nessa aresta?

Answer 14

Ψg(ex)=4,4

Lacete no vertice 44, labeled como aresta ex

Question 15

Como se caracteriza um grafo?

Que coisas fazem um grafo um grafo?

Answer 15

Conjunto de Vertices - V(G)
Conjunto de Arestas - E(G)
Funcao Incidencia - Ψg

Onde V e E sao conjuntos dijuntos (nao tem nenhum elemento em comum).

Onde Ψ e uma funcao que para cada aresta pertencente a E faz corresponder um par ordenado de elementos, ou seja os vertices que a aresta liga.

Se G for um grafo orientado, E passa a designar-se pelo conjunto de arcos.

Question 16

Vertices Adjacentes?

Answer 16

Sao caracterizados por terem a mesma aresta.

Isto e dados dois vertices u e v, u e v sao vertices extremos de uma aresta, se estiverem ligados na funcao de incidencia.

Logo se sao vertices extremos, estando ligados pela mesma aresta dizem-se vertices adjacentes.

Question 17

Arestas Adjacentes?

Answer 17

Sao arestas que incidem no mesmo vertice.

Question 18

Arestas paralelas na funcao indicencia tem os mesmos vertices?

Answer 18

Sim

Question 19

Vizinhanca?

Como se representa?

Answer 19

A vizinhanca de um vertice v, e dada pelo conjunto de vertices adjacentes a v, isto e aqueles vertices aos quais v esta ligado pela mesma aresta. Podem ser varios, desde que o par de vertices seja ligado por uma unica aresta de uma vez.

Representa-se da seguinte maneira N(v)

Question 20

Como se caracteriza um grafo (digrafo) simples?

Answer 20

Nao contem arestas paralelas nem lacetes.

No caso de um grafo simples, este pode ser definido unicamente pelo conjunto de vertices e pelo conjunto das arestas.

Question 21

Ordem de um grafo?

Answer 21

E o numero de vertices de um grafo G. Representado por μ ou por v

Question 22

Dimensao de um grafo?

Answer 22

Numero de arestas de um grafo G, designado por epsilon (ε)

Question 23

Quando e que existe igualdade de grafos?

Answer 23

Quando o as suas ordens, dimensoes e funcoes de incidencia sao iguais.

Question 24

Como se caracteriza um grafo simples complementar?

Answer 24

E um grafo no qual dois vertices sao adjacentes se nao forem no grafo original.

A juncao do grafo original com o complementa da um grafo completo.

Question 25

Grau de um vertice?

Grau de um lacete?

Como se representa? Maior e o menor?

Answer 25

Sera o numero de arestas incidentes num dado vertice v.
No caso de a aresta ser lacete conta duas vezes.

Representa-se da seguinte maneira: dg(v)

Maior grau dos vertices: ∆(G)
Menor grau dos vertices: δ(G)

Question 26

Semigrau de entrada e saida de um grafo orientado?

Answer 26

Semigrau de entrada: Vertice do qual vem, vertice para o qual chegou. Numero de arcos que apontam para o vertice.
Representado por um -

Semigrau de saida: Vertice do qual parte para aquele que vai. Numero de arcos que saiem do vertice.
Representado por um +

Question 27

Teorema que relaciona o grau dos vertices com o numero de arestas?

Answer 27

A soma dos graus de cada um dos vertices do grafo G e igual ao dobro do numero total de arestas do grafo G.

Corolario: O numero de vertices de grau impar e par.
Entao o semigrau de saida e de entrada sao iguais entre si e iguais ao numero de arestas do grafo.

Question 28

Matriz de Adjacencia?

Como se representa?

Qual a sua dimensao?

Se houver um lacete num grafo nao orientado que valor tem?

Se houver arestas paralelas que valor tem?

Como se organizam as entradas num grafo orientado?

Se houver lacetes num grafo orientado?

O que podemos concluir a cerca da matriz de adjacencia se o grafo nao for orientado?

Answer 28

Representa-se por A(H)

Uma matriz quadrada de dimensao v x v. Representa o numero de arestas entre um dado vertice.

Se houver um lacete a diagonal da matriz nesse ponto tera o valor de 2.

No caso de haver arestas paralelas entre vertices contabilizam-se normalmente, isto e, se entre dois vertices houver 2 arestas paralelas entao na entrada ij da matriz colocamos 2.

Se G for um grafo orientado, entao a entrada ij na matriz e dada pelo numero de arcos com cauda no vertice vi e cabeca no vertice vj.

Num grafo orientado representamos na coluna desse vertice quais sao os que incidem nele.

Isto e por exemplo se um vertice 2 estiver ligado com o vertice 3 (orientado de 2 para 3) entao entrada 23 na matriz de adjacencia sera de 1.

Se houver lacetes o numero na entrada da matriz e igual ao numero de lacetes num grafo orientado.

Se o grafo nao for orientado entao a matriz e simetrica

Question 29

Matriz Incidencia Aresta-Vertice?

Como se representa?

Qual a sua dimensao?

Que valor se coloca se dois vertices forem ligados pela mesma aresta? E os que nao estao?

E se houver lacetes?

E no caso do grafo ser orientado? Quais serao os valores?

Answer 29

Representa-se por M(G)

Matriz de dimensao v x ε tal que a cada entrada da matriz faz corresponder na coluna da aresta aqueles vertices que liga (colocando o valor 1 a cada um dos vertices). E claro nos vertices aos quais a aresta nao esta ligada colocamos 0 nessa entrada.

Se houver lacetes estes contam apenas como 1

No caso do grafo ser orientado, colocamos o valor 1 onde comeca e o valor -1 onde acaba, isto e 1 na cauda e -1 na cabeca da aresta. Ou seja, liga os vertices extremos.

Question 30

Lista de arestas?

Como se representa esta lista de um grafo de 4 arestas ?

Answer 30

Armazena numa lista todas as arestas do grafo.

No caso de um grafo H a lista de arestas sera, por exemplo:

[ad, ab, bc, cd, ac]

Question 31

Lista de sucessores/Lista de Adjacencia?

Se for um grafo orientado como se organiza a lista?

Answer 31

Caracterizada por fazer corresponder a cada um dos vertices uma lista de todos os seus vertices adjacentes.

Ou ainda todos os vertices que sao a cabeca de um arco com cauda v, isto e se de um vertice v sairem varios arcos a lista de sucessores desse mesmo vertice contem todos os vertices que esse arco atinge. (os vertices que sao “adjacentes”)

Question 32

Multigrafo?

Answer 32

Sera um grafo com arestas multiplas e/ou lacetes.

Question 33

Isomorfismo?

Quando e que dois grafos sao isomorfos?

Como se representa?

Answer 33

Grafos que, com omissao dos vertices e arestas, admitem representacoes identicas.

Mais concretamente, dois grafos dizem-se isomorfos se existirem duas bijecoes que relacionem os vertices e as arestas de cada um.

Dois grafos dizem-se isomorfos se existe uma bijecção entre os respectivos conjuntos de vértices e uma bijecção entre os respectivos conjuntos de arestas que preservam as relações de adjacência e de incidência.

(ψg(e)=uv) se e so se (ψh(θ(e))=ϕ(u)ϕ(v))

Representa-se da seguinte maneira: G~=H

Question 34

Automorfismo?

No que difere com o isomorfismo?

Answer 34

Designa se um automorfismo de um grafo G se a bijecao ϕ : V(G)-V(G) preserva o numero de arestas entre pares de vertices. Relacao entre o proprio grafo.

Se G for um grafo simples, entao um automorfismo e um isomorfismo de G em G.

Se G for um multigrafo (grafo com arestas multiplas e/ou lacetes) podem existir varios isomorfismos entre G e G

Qualquer grafo tem admite pelo menos um automorfismo dado pela funcao identidade.

Question 35

Passeios em Grafos?

Podem-se repetir arestas? E os vertices?

Answer 35

Uma sequencia P = v0 e1 v1 e2 … ek vk. Passeio entre v0 e vk

onde v0 e v1 sao extremos da aresta e1, ou seja, saimos de um vertice percorremos a aresta que tem, espetamos la o outro vertice extremo e assim sucessivamente.

Podem haver arestas e vertices repetidos.

Question 36

Trajeto?

Answer 36

E um passeio sem arestas repetidas.

Question 37

Caminho?

Quando e que um caminho e fechado?

Answer 37

E um passeio sem vertices repetidos a execao do primeiro e do ultimo.

Um caminho e fechado quando o vertice final coincide com o inicial.

Question 38

Cicuito/ciclo?

Answer 38

Um ciclo e um caminho fechado, isto e o vertice inicial e identico ao final.

Question 39

Comprimento de caminhos, passeios e trajetos?

Answer 39

O comprimento de um passeio e dado pelo numero de arestas que o constitui (repetidas ou nao).

O comprimento dos caminhos e nos trajetos coicide com o numero de arestas.

Ex: Uma aresta e uma caminho de comprimento 1 e um vertice e um caminho de comprimento 0.

Question 40

O que define a distancia entre vertices?

Teorema da distancia?

Answer 40

Sera o menor caminho existente entre os dois vertices.

Se nao houver caminho entre eles diz se que o caminho tem distancia infinita.

Se o menor grau dos vertices δ(G)>=2 entao o grafo G contem um caminho P e um ciclo C, tais que:

comp(P)>=δ(G)
comp(C)>=δ(G)+1

Question 41

Cintura de um grafo?

Como se representa?

Se nao houver cintura, o que acontece?

Answer 41

Sera o comprimento do circuito de menor comprimento. Se existir denota-se por g(G) [gurth].

Se nao existir denota-se por g(G)=∞

Question 42

Excentricidade de um vertice?

Como se representa?

Answer 42

A maior distancia entre um vertice v do grafo G e todos os outros vertices do grafo. Cada vertice tem um excentricidade.

Inclui todos os vertices e nao so os adjacentes.

Representa-se por eG(v) ou ainda

e(v) = max distG(u,v)

Question 43

Diametro de um grafo?

Como se representa?

Answer 43

O diametro de um grafo sera a maior excentricidade dos seus vertices.

Representa-se da seguinte forma:

diam(G)

Question 44

Raio de um grafo?

Como se representa?

Answer 44

Sera a menor excentricidade dos seus vertices.

Representa-se da seguinte forma:

r(G)

Question 45

Vertice Central e Centro?

Answer 45

Um vertice diz-se central se a sua distancia ao vertice mais distante e minima.

Ou seja, a maior distancia (excentricidade / eG(v)) sera igual ao raio (o menor das excentricidades).

Question 46

Subgrafo?

O que acontece com as arestas, os vertices e as funcoes de incidencia?

Answer 46

Um grafo H e subgrafo de um grafo G se:

Os seus vertices e as suas arestas estiverem incluidos nos respetivos conjuntos V(G) e E(G)

Se a funcao de incidencia de H for a restricao da funcao de incidencia de G ao conjunto E(H)

Question 47

Subgrafo Abrangente/Subgrafo de Suporte?

Tem de ter o mesmo numero de arestas?

Como se representa?

Como se distingue do subgrafo induzido pelas arestas?

Answer 47

Um subgrafo H que esta incluido em G e que V(H) = V(G)

Nao necessita de ter as mesmas arestas.

Representa-se da seguinte maneira G - E^

O conjunto de arestas sera E-E^
(E - Arestas do grafo original, E^ - arestas do subgrafo)

Em geral G[E -E^] e G - E^ são distintos.

Question 48

Subgrafo Induzido?

Como se representa? E se for so com um vertice?

Answer 48

Subgrafo H cujo conjunto de vertices esta incluido em V(G) e cujo conjunto de arestas coincide com as arestas de G com os extremos no conjunto de vertices de H.

Denota-se por G[V - V^] ou, simplesmente, G - V^ o subgrafo induzido após a eliminação dos vértices do subconjunto V^ e de todas as arestas que incidiam no conjunto V^.

Com um unico vertice: G - V ou v

Isto e, sera um grafo com menos vertices mas que preserva as arestas, com os mesmos extremos.

Question 49

Subgrafo Induzido pelas arestas?

Como se representa?

Answer 49

Dado um subconjunto das arestas E^, o subgrafo induzido por esse mesmo conjunto denota-se por G[E^] e sera o grafo cujo conjunto de arestas sera E^ e cujos vertices serao os extremos das arestas de E^

Isto e se se preservam os extremos de um subconjunto de arestas entao o subgrafo induzido contem os vertices extremos das arestas que estao contidas no subconjunto.

Question 50

Vertices Conexos?

Answer 50

Sao conexos de existir um caminho entre (u,v) em G.

Num grafo conexo todos os pares de vertices distintos sao conexos.

Question 51

Componente Conexa?

Notacao?

Relacao da conexividade com o numero de arestas?

Answer 51

Sera o subgrafo induzido por cada um dos vertices.

P.ex

De V(G) tem-se as classes de equivalencia de cada um dos vertices que, se forem conexos, terao todos a mesma classe de equivalencia

Uma componente conexa de G sera o subgrafo induzido por G[V1]. Ou seja, sera um subgrafo que contem todos os vertices que sao conexos entre si.

cc(G) denota o numero de componentes conexas de um grafo G. Se o grafo for conexo tera apenas uma componente conexa.

Se G for um grafo conexo de ordem n (com n vertices) entao E(G)>= n-1

Question 52

Grafo Completo?

Answer 52

Um grafo onde todos os pares de vertices sao adjacentes.

Ou seja, escolhendo um par de vertices ao acaso de um grafo completo, por ser completo garante que os vertices sao adjacentes.

Um grafo nulo nao tem arestas.

Question 53

Grafo Regular?

Answer 53

Se todos os vertices do grafo tiverem o mesmo grau, esse grafo e regular de ordem k, onde k e o grau dos vertices.

Question 54

Marca de um vertice?

Answer 54

Comprimento do caminho mais curto entre um vertice v (o da marca) e um outro vertice s dos caminhos ja determinados.

Vertice permanente no algoritmo de Dijkstra.

Question 55

Antecessor de um vertice?

Answer 55

Antecessor de um vertice v no caminho mais curto entre um vertice s e o vertice v entre os ja determinados.

De onde viemos basicamente.

Question 56

Arvore?

Answer 56

Grafo sem ciclos.

Contem V-1 arestas.

E conexa e cada aresta e uma ponte.

Entre um par de vertices de uma arvore existe apenas um caminho entre eles.

Se acrescentarmos uma aresta a arvore obtemos um ciclo.

Question 57

Floresta?

Answer 57

Um grafo simples diz-se floresta se nao contem circuitos, pode ser desconexo.

Isto e uma floresta e um conjunto de arvores que nao estao ligadas entre si. Logo a floresta nao e conexa.

Um grafo diz-se floresta se o numero de arestas menos o numero de vertices mais o numero de componentes conexas for igual a zero, isto e:

ε(G) -v(G) + cc(G) = 0

Question 58

Fusao de extremos de uma aresta?

Answer 58

Representado por G//e

Contracao de uma aresta apenas no facto de, com exepcao da aresta contraida, todas as restante se mantem no grafo (incluindo quaisqueres lacetes ou arestas paralelas).

A aresta e desaparece e se a aresta e for paralela com uma outra a outra aresta fica como lacete.

A operacao de fusao comuta com a eliminacao de arestas, isto e, dadas duas arestas e e f:

(G//e) - f = (G-f)//e

Question 59

Teorema do Numero de Arvores Abrangentes?

Se G nao for conexo?
Se G e uma arvore?
Se G e um ciclo, com k arestas?
Se G e um grafo de dois vertices ligado por k arestas?
Se G resultar de dois subgrafos G1 e G2 unidos por uma ponte, ou por um unico vertice em comum?

Answer 59

t(G) = t(G-e) + t(G//e)

Se um grafo G nao e conexo, entao t(G)=0
Se G e uma arvore, entao t(G)=1
Se G e um ciclo, com k arestas, entao t(G)=k
Se G e um grafo de dois vertices ligado por k arestas, entao t(G)=k
Se G resultar de dois subgrafos G1 e G2 unidos por uma ponte, ou por um unico vertice em comum, entao t(G) = t(G1)*t(G2)

Question 60

Contracao de uma aresta?

Answer 60

Representa-se por G/e

Os vertices extremos dessa aresta sao contraidos num unico vertice.

Todas as arestas paralelas e lacetes sao eliminados (aqueles que iram ser profuzidos eventualmente se fosse uma fusao).