04 subgrafos

Prévia do material em texto

Otimização em Redes
Allexandre Fortes S. Reis
Coordenadoria de Engenharia de Produção
Departamento de Engenharia Mecânica
Campus Santo Antônio
Universidade Federal de São João Del Rei
5 de setembro de 2017
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 1 / 38
Conteúdo
1
Subgrafos
2
Conectividade e Caminhos
3
Alcançabilidade
4
Conexidade ou Conectividade
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 2 / 38
Subgrafo
Definição
Um grafo Gs = (Vs, As) é dito ser um subgrafo de um grafo G = (V, A)
se todos os vértices e todas as arestas de Gs estão em G, ou seja, se
Vs ⊆ V e As ⊆ A
Observações:
Todo grafo é subgrafo de si próprio;
O subgrafo Gs2 de um subgrafo Gs de G também é subgrafo de G;
Um vértice simples de G é um subgrafo de G;
Uma aresta simples de G (juntamente com suas extremidades) é um
subgrafo de G.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 3 / 38
Subgrafo
Encontre todos os subgrafos.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 4 / 38
Subgrafos
Subgrafos Disjuntos de Arestas
Dois (ou mais) subgrafos g1 e g2 de um grafo G são disjuntos de arestas se
g1 e g2 não tiverem nenhuma aresta em comum.
g1 e g2 podem ter vértices em comum ?
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 5 / 38
Subgrafos
Subgrafos Disjuntos de Vértices
Dois (ou mais) subgrafos g1 e g2 de um grafo G são disjuntos de vértices
se g1 e g2 não tiverem nenhum vértice em comum.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 6 / 38
Subgrafos
Subgrafo Induzido por Vértices
Contém um subconjunto dos vértices do grafo original e todas as ligações
entre eles que figurarem no mesmo grafo.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 7 / 38
Subgrafos
Subgrafo Induzido por Arestas
Contém um subconjunto das arestas do grafo original e todos os vértices
adjacentes a elas no mesmo grafo.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 8 / 38
Definições
Passeio ou percurso
Um passeio é uma sequência finita de vértices e arestas. Cada vértice da
sequência é incidente a aresta que o precede e a aresta seguinte. Essa sequência
deve acabar e iniciar em um vértice (não necessariamente os mesmos).
Ex.:
1 - a - 2 - c - 3 - d - 4 - d - 3 - e - 5
ou: 1 - 2 - 3 - 4 - 3 - 5
O Passeio pode ser:
aberto : quando inicia e acaba em vértices
diferentes (o caso acima)
fechado : quando inicia e acaba no mesmo vértice.
Ex.: 1-2-3-4-3-5-3-1
1 2
3 4
5
a
b c
d
e
a
c
dd
e
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 9 / 38
Definições
Passeio ou percurso
Um passeio é uma sequência finita de vértices e arestas. Cada vértice da
sequência é incidente a aresta que o precede e a aresta seguinte. Essa sequência
deve acabar e iniciar em um vértice (não necessariamente os mesmos).
Ex.: 1 - a - 2
- c - 3 - d - 4 - d - 3 - e - 5
ou: 1 - 2 - 3 - 4 - 3 - 5
O Passeio pode ser:
aberto : quando inicia e acaba em vértices
diferentes (o caso acima)
fechado : quando inicia e acaba no mesmo vértice.
Ex.: 1-2-3-4-3-5-3-1
1 2
3 4
5
a
b c
d
e
a
c
dd
e
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 9 / 38
Definições
Passeio ou percurso
Um passeio é uma sequência finita de vértices e arestas. Cada vértice da
sequência é incidente a aresta que o precede e a aresta seguinte. Essa sequência
deve acabar e iniciar em um vértice (não necessariamente os mesmos).
Ex.: 1 - a - 2 - c - 3
- d - 4 - d - 3 - e - 5
ou: 1 - 2 - 3 - 4 - 3 - 5
O Passeio pode ser:
aberto : quando inicia e acaba em vértices
diferentes (o caso acima)
fechado : quando inicia e acaba no mesmo vértice.
Ex.: 1-2-3-4-3-5-3-1
1 2
3 4
5
a
b c
d
e
a
c
dd
e
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 9 / 38
Definições
Passeio ou percurso
Um passeio é uma sequência finita de vértices e arestas. Cada vértice da
sequência é incidente a aresta que o precede e a aresta seguinte. Essa sequência
deve acabar e iniciar em um vértice (não necessariamente os mesmos).
Ex.: 1 - a - 2 - c - 3 - d - 4
- d - 3 - e - 5
ou: 1 - 2 - 3 - 4 - 3 - 5
O Passeio pode ser:
aberto : quando inicia e acaba em vértices
diferentes (o caso acima)
fechado : quando inicia e acaba no mesmo vértice.
Ex.: 1-2-3-4-3-5-3-1
1 2
3 4
5
a
b c
d
e
a
c
d
d
e
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 9 / 38
Definições
Passeio ou percurso
Um passeio é uma sequência finita de vértices e arestas. Cada vértice da
sequência é incidente a aresta que o precede e a aresta seguinte. Essa sequência
deve acabar e iniciar em um vértice (não necessariamente os mesmos).
Ex.: 1 - a - 2 - c - 3 - d - 4 - d - 3
- e - 5
ou: 1 - 2 - 3 - 4 - 3 - 5
O Passeio pode ser:
aberto : quando inicia e acaba em vértices
diferentes (o caso acima)
fechado : quando inicia e acaba no mesmo vértice.
Ex.: 1-2-3-4-3-5-3-1
1 2
3 4
5
a
b c
d
e
a
c
dd
e
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 9 / 38
Definições
Passeio ou percurso
Um passeio é uma sequência finita de vértices e arestas. Cada vértice da
sequência é incidente a aresta que o precede e a aresta seguinte. Essa sequência
deve acabar e iniciar em um vértice (não necessariamente os mesmos).
Ex.: 1 - a - 2 - c - 3 - d - 4 - d - 3 - e - 5
ou: 1 - 2 - 3 - 4 - 3 - 5
O Passeio pode ser:
aberto : quando inicia e acaba em vértices
diferentes (o caso acima)
fechado : quando inicia e acaba no mesmo vértice.
Ex.: 1-2-3-4-3-5-3-1
1 2
3 4
5
a
b c
d
e
a
c
dd
e
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 9 / 38
Definições
Passeio ou percurso
Um passeio é uma sequência finita de vértices e arestas. Cada vértice da
sequência é incidente a aresta que o precede e a aresta seguinte. Essa sequência
deve acabar e iniciar em um vértice (não necessariamente os mesmos).
Ex.: 1 - a - 2 - c - 3 - d - 4 - d - 3 - e - 5
ou: 1 - 2 - 3 - 4 - 3 - 5
O Passeio pode ser:
aberto : quando inicia e acaba em vértices
diferentes (o caso acima)
fechado : quando inicia e acaba no mesmo vértice.
Ex.: 1-2-3-4-3-5-3-1
1 2
3 4
5
a
b c
d
e
a
c
dd
e
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 9 / 38
Definições
Passeio ou percurso
Um passeio é uma sequência finita de vértices e arestas. Cada vértice da
sequência é incidente a aresta que o precede e a aresta seguinte. Essa sequência
deve acabar e iniciar em um vértice (não necessariamente os mesmos).
Ex.: 1 - a - 2 - c - 3 - d - 4 - d - 3 - e - 5
ou: 1 - 2 - 3 - 4 - 3 - 5
O Passeio pode ser:
aberto : quando inicia e acaba em vértices
diferentes (o caso acima)
fechado : quando inicia e acaba no mesmo vértice.
Ex.: 1-2-3-4-3-5-3-1
1 2
3 4
5
a
b c
d
e
a
c
dd
e
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 9 / 38
Definições
Cadeia
Um passeio que não repete arestas.
Ex.: 4 - 3 - 2 - 1 - 3 - 5
1 2
3 4
5
a
b c
d
e
d
c
a
b
e
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 10 / 38
Definições
Cadeia
Um passeio que não repete arestas.
Ex.: 4 - 3 - 2 - 1 - 3 - 5
1 2
3 4
5
a
b c
d
e
d
c
a
b
eAllexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 10 / 38
Definições
Cadeia
Um passeio que não repete arestas.
Ex.: 4 - 3 - 2 - 1 - 3 - 5
1 2
3 4
5
a
b c
d
e
d
c
a
b
e
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 10 / 38
Definições
Cadeia
Um passeio que não repete arestas.
Ex.: 4 - 3 - 2 - 1 - 3 - 5
1 2
3 4
5
a
b c
d
e
d
c
a
b
e
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 10 / 38
Definições
Cadeia
Um passeio que não repete arestas.
Ex.: 4 - 3 - 2 - 1 - 3 - 5
1 2
3 4
5
a
b c
d
e
d
c
a
b
e
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 10 / 38
Definições
Cadeia
Um passeio que não repete arestas.
Ex.: 4 - 3 - 2 - 1 - 3 - 5
1 2
3 4
5
a
b c
d
e
d
c
a
b
e
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 10 / 38
Definições
Caminho
Uma cadeia sem repetição de vértices.
Ex.: 1 - 2 - 3 - 5
aberto : quando inicia e acaba em
vértices diferentes (o caso
acima)
fechado : quando inicia e acaba no
mesmo vértice. Ex.: 1-2-3-1.
comprimento : o comprimento de um
caminho é o
número de arestas que o
mesmo inclui.
1 2
3 4
5
a
b c
d
e
a
c
e
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 11 / 38
Definições
Caminho
Uma cadeia sem repetição de vértices.
Ex.: 1 - 2 - 3 - 5
aberto : quando inicia e acaba em
vértices diferentes (o caso
acima)
fechado : quando inicia e acaba no
mesmo vértice. Ex.: 1-2-3-1.
comprimento : o comprimento de um
caminho é o
número de arestas que o
mesmo inclui.
1 2
3 4
5
a
b c
d
e
a
c
e
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 11 / 38
Definições
Caminho
Uma cadeia sem repetição de vértices.
Ex.: 1 - 2 - 3 - 5
aberto : quando inicia e acaba em
vértices diferentes (o caso
acima)
fechado : quando inicia e acaba no
mesmo vértice. Ex.: 1-2-3-1.
comprimento : o comprimento de um
caminho é o
número de arestas que o
mesmo inclui.
1 2
3 4
5
a
b c
d
e
a
c
e
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 11 / 38
Definições
Caminho
Uma cadeia sem repetição de vértices.
Ex.: 1 - 2 - 3 - 5
aberto : quando inicia e acaba em
vértices diferentes (o caso
acima)
fechado : quando inicia e acaba no
mesmo vértice. Ex.: 1-2-3-1.
comprimento : o comprimento de um
caminho é o
número de arestas que o
mesmo inclui.
1 2
3 4
5
a
b c
d
e
a
c
e
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 11 / 38
Definições
Caminho
Uma cadeia sem repetição de vértices.
Ex.: 1 - 2 - 3 - 5
aberto : quando inicia e acaba em
vértices diferentes (o caso
acima)
fechado : quando inicia e acaba no
mesmo vértice. Ex.: 1-2-3-1.
comprimento : o comprimento de um
caminho é o
número de arestas que o
mesmo inclui.
1 2
3 4
5
a
b c
d
e
a
c
e
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 11 / 38
Definições
Caminho
Uma cadeia sem repetição de vértices.
Ex.: 1 - 2 - 3 - 5
aberto : quando inicia e acaba em
vértices diferentes (o caso
acima)
fechado : quando inicia e acaba no
mesmo vértice. Ex.: 1-2-3-1.
comprimento : o comprimento de um
caminho é o
número de arestas que o
mesmo inclui.
1 2
3 4
5
a
b c
d
e
a
c
e
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 11 / 38
Relembrando...
Passeio
Sequência finita de vértices e arestas.
Cadeia
Um passeio que não repete arestas.
Caminho
Uma cadeia sem repetição de vértices.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 12 / 38
Caminhos e Circuitos
Teorema 1
Se um grafo possui exatamente 2 vértices de grau ímpar, existe um
caminho entre esses dois vértices.
Teorema 2
O número mínimo de arestas de um grafo simples com n vértices e k
componentes é n− k.
Teorema 3
Um grafo simples com n vértices e k componentes possui no máximo
(n− k)(n− k + 1)/2 arestas (caso trivial);
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 13 / 38
Caminhos e Circuitos
Teorema 1
Se um grafo possui exatamente 2 vértices de grau ímpar, existe um
caminho entre esses dois vértices.
Teorema 2
O número mínimo de arestas de um grafo simples com n vértices e k
componentes é n− k.
Teorema 3
Um grafo simples com n vértices e k componentes possui no máximo
(n− k)(n− k + 1)/2 arestas (caso trivial);
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 13 / 38
Caminhos e Circuitos
Teorema 1
Se um grafo possui exatamente 2 vértices de grau ímpar, existe um
caminho entre esses dois vértices.
Teorema 2
O número mínimo de arestas de um grafo simples com n vértices e k
componentes é n− k.
Teorema 3
Um grafo simples com n vértices e k componentes possui no máximo
(n− k)(n− k + 1)/2 arestas (caso trivial);
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 13 / 38
Ciclos
Definição
Um ciclo é um caminho fechado.
Alguns autores, utilizam o termo circuito para o caso de grafos orientados.
Grafo Ciclo: Um grafo ciclo Cn é um grafo com n vértices formado por
apenas um ciclo passando por todos os vértices.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 14 / 38
Ciclos
Definições
A cintura de um grafo é o comprimento do menor ciclo existente no mesmo.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 15 / 38
Ciclos
Definições
A circunferência de um grafo é o comprimento do maior ciclo existente no
mesmo.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 16 / 38
Alcançabilidade
Definição
Um vértice w é alcançável a partir do vértice v se houver um caminho
entre w e v.
Definição
O conjunto de vértices alcançáveis a partir de v é, portanto, formado pelos
sucessores de v, os sucessores dos sucessores e assim por diante.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 17 / 38
Alcançabilidade
Definição
Um vértice w é alcançável a partir do vértice v se houver um caminho
entre w e v.
Definição
O conjunto de vértices alcançáveis a partir de v é, portanto, formado pelos
sucessores de v, os sucessores dos sucessores e assim por diante.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 17 / 38
Alcançabilidade
Transitividade
Se w é alcançável a partir de v;
e se x é alcançável de w;
então x é alcançável a partir de v.
Transitividade
Relação de Alcançabilidade é transitiva.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 18 / 38
Alcançabilidade
Transitividade
Se w é alcançável a partir de v;
e se x é alcançável de w;
então x é alcançável a partir de v.
Transitividade
Relação de Alcançabilidade é transitiva.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 18 / 38
Fecho Transitivo de um Vértice - Grafo Não Direcionado
Definição
O Fecho Transitivo de um vértice v (denotado por Γˆ(v)) é o conjunto dos
vértices de um grafo alcançáveis a partir de v.
Γˆ(1) = {2, 3, 4}
Γˆ(5) = {}
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 19 / 38
Fecho Transitivo de um Vértice - Grafo Direcionado
Fecho Transitivo Direto
O Fecho Transitivo Diretode um vértice v (denotado por Γˆ+(v)) é o
conjunto dos vértices de um grafo alcançáveis a partir de v.
Os vértices em Γˆ+(v) são chamados de descendentes de v.
Fecho Transitivo Indireto
O Fecho Transitivo Indireto de um vértice v (denotado por Γˆ−(v)) é o
conjunto dos vértices de um grafo a partir dos quais v é alcançável.
Os vértices em Γˆ−(v) são chamados de ascendentes de v.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 20 / 38
Fecho Transitivo Direto e Indireto
Γˆ+(1) = {2, 3, 4, 5, 7, 9, 10, 13}
Γˆ−(10) = {1, 4}
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 21 / 38
Conexidade em Grafos Não Direcionados
Definição
Em um GND conexo, todos os vértices são alcançáveis a partir de qualquer
outro.
Em um GND conexo, sempre é possível fazer um passeio fechado que
inclua todos os vértices.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 22 / 38
Conexidade
Ponte
Uma ponte de um grafo G é uma aresta cuja remoção resulta no aumento
do número de componentes de G.
A aresta u1 é uma ponte. As arestas u3 e u2 não são.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 23 / 38
Conexidade em Grafos Direcionados
Grafo Simplesmente Conexo: s-conexo
O grafo subjacente não-direcionado obtido através da substituição de todas
as arestas de G por arestas não direcionadas é um grafo conexo.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 24 / 38
Conexidade em Grafos Direcionados
Grafo Semi-Fortemente Conexo: sf-conexo
Para cada par de vértices (v1, v2), existe um caminho de v1 para v2 ou de
v2 para v1.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 25 / 38
Conexidade em Grafos Direcionados
Grafo Fortemente Conexo: f-conexo
Para cada par de vértices (v1, v2), existe um caminho direcionado de v1
para v2 e de v2 para v1.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 26 / 38
Conexidade ou Conectividade
Exemplo
Conceito aplicado a Grafos Não Direcionados;
Indica o quanto um grafo é conexo.
Definição
A conexidade ou conectividade κ(G) de um grafo G = (V,E) é o menor
número de vértices cuja remoção desconecta G ou o reduz a um único
vértice.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 27 / 38
Conexidade ou Conectividade
Exemplo
Conceito aplicado a Grafos Não Direcionados;
Indica o quanto um grafo é conexo.
Definição
A conexidade ou conectividade κ(G) de um grafo G = (V,E) é o menor
número de vértices cuja remoção desconecta G ou o reduz a um único
vértice.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 27 / 38
Conexidade ou Conectividade
Exemplos de remoções de conjuntos de vértices que desconectam o grafo.
Neste caso, κ(G) = 1 (Figura 2).
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 28 / 38
Conexidade ou Conectividade
Grafos Completos
Para grafos completos com n vértices, κ(Kn) = n− 1.
Grafos Não Completos
Para grafos não completos haverá um par (v1, v2) de vértices não
adjacentes, então temos que:
κ(G) ≤ n− 2 ∀G 6= Kn
Limite superior para κ(G) em qualquer grafo:
κ(G) ≤ δ(G)a
aδ(G) : menor grau em um GND.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 29 / 38
Conexidade ou Conectividade
Grafos Completos
Para grafos completos com n vértices, κ(Kn) = n− 1.
Grafos Não Completos
Para grafos não completos haverá um par (v1, v2) de vértices não
adjacentes, então temos que:
κ(G) ≤ n− 2 ∀G 6= Kn
Limite superior para κ(G) em qualquer grafo:
κ(G) ≤ δ(G)a
aδ(G) : menor grau em um GND.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 29 / 38
Conexidade ou Conectividade
Grafos Completos
Para grafos completos com n vértices, κ(Kn) = n− 1.
Grafos Não Completos
Para grafos não completos haverá um par (v1, v2) de vértices não
adjacentes, então temos que:
κ(G) ≤ n− 2 ∀G 6= Kn
Limite superior para κ(G) em qualquer grafo:
κ(G) ≤ δ(G)a
aδ(G) : menor grau em um GND.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 29 / 38
Conexidade ou Conectividade
Caminhos Disjuntos
Dois percursos entre os vértices v e w de um grafo são disjuntos se não
houver interseção de arestas.
Teorema
Um grafo G = (V,E) é k-conexo se e somente se para todo para
v, w ∈ V, v 6= w existirem ao menos k percursos disjuntos.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 30 / 38
Conexidade ou Conectividade
1-Conexo 2-Conexo 3-Conexo
Grafo k-conexo
Para todo grafo k-conexo:
κ(G) ≤ δ(G)
κ(G) ≤ k
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 31 / 38
Conexidade ou Conectividade
Grafo k-conexo
Grafo borboleta: 2-conexo
K7: 6-conexo, mas também é 1-conexo, 2-conexo, 3-conexo, 4-conexo,
5-conexo...
k ≥ κ(G) ≤ δ(G)
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 32 / 38
Exercícios
1) Quantos caminhos existem entre os vértices b e f?
2) Dê um exemplo de um grafo conexo G cuja remoção de qualquer aresta
torna G desconexo. Quantas arestas possui um grafo com estas
características?
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 33 / 38
Exercícios
3) Com relação ao grafo abaixo, responda:
a) O grafo é simples?
b) Completo?
c) Regular?
d) Conexo?
e) Encontre 2 caminhos entre v3 e v6.
f) Encontre 1 ciclo.
g) Indique 1 aresta cuja remoção tornará o grafo desconexo.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 34 / 38
Exercício
4) Quantos grafos ciclos (não isomorfos) são subgrafos do grafo abaixo?
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 35 / 38
Exercícios
5) Qual a cintura e a circunferência do grafo abaixo ?
6) Mostre que não é possível ter um grupo de 7 pessoas no qual cada um
conhece exatamente outras 3 pessoas.
7) Prove que quaisquer dois grafos conexos com n vértices, todos de grau
2, são isomorfos.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 36 / 38
Dúvidas? Valar joll	oris
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 37 / 38
Referências
(1) Notas de aula Professor Dr. Marco Antônio Carvalho (DECOM/UFOP);
(2) Notas de aula Professor Dr. Gustavo Peixoto (DECOM/UFOP);
(3) Goldbarg, Marco e Goldbarg, Elizabeth. Grafos: Conceitos, algoritmos e apli-
cações (2012);
(4) Taha, Hamdy. Pesquisa Operacional (2008);
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 38 / 38
	Subgrafos
	Conectividade e Caminhos
	Alcançabilidade
	Conexidade ou Conectividade