[[cap4]]
== Introdução a Grafos e Árvores

:cap: cap4
:online: {gitrepo}/blob/master/livro/capitulos/code/{cap}
:local: {code_dir}/{cap}
:img: {img_dir}/{cap}

.Objetivos do capítulo
____
Ao final deste capítulo você deverá ser capaz de (entre outras coisas):

* Modelar problemas do seu mundo real por meio de grafos, digrafos, ou
  árvores, para mais facilmente resolver os problemas mais simples;
* Dominar e saber usar os principais conceitos e terminologia de
  grafos, de digrafos e de árvores;
* Reconhecer se um grafo é k-partido, k-clique, conexo ou desconexo,
  digrafo, ou subgrafo de outro grafo;
* Dominar e saber usar os principais conceitos e terminologia de
  passeios, trilhas, ciclos, caminhos, grafos eulerianos e
  hamiltonianos;
* Conhecer os problemas do caminho mais curto, do carteiro chinês, do
  caixeiro viajante, das árvores geradoras de grafos. Não precisará
  saber os algoritmos, que são difíceis, mas deverá saber encontrar
  soluções _ad hoc_ de problemas em grafos muito pequenos.

____

*Nosso objetivo, neste capítulo*, é que você seja introduzido aos
conceito básicos sobre grafos e árvores, começando a desenvolver a
capacidade de modelar problemas reais por meio deles, e capacitando-o
a acompanhar disciplinas posteriores que o habilitarão a modelar
mais complexos problemas reais usando tais ferramentas, depois
resolvê-los usando os algoritmos mais apropriados. Por falta de
tempo, de espaço no livro, e de sua maior experiência com
linguagens de programação, deixaremos a maioria dos tais algoritmos
mais interessantes (e difíceis) para quando você fizer as
disciplinas _Estruturas de Dados_, _Redes de Computadores_, e, talvez
como ouvinte, alguma disciplina na linha de _Análise_ (da
complexidade) e _Projeto de Algoritmos_, do Bacharelado em Ciência
da Computação, da UFPB.

.Sempre vamos repetir
[TIP]
====
Estamos torcendo por você. O fórum de alunos, os tutores, e eu (o
professor) queremos e vamos ajudá-lo (nessa ordem), mas você tem
que ser determinado e disciplinado, *cada semana dedicando 4 a 8
horas para estudar este livro*.
====

[NOTE]
====
Agradecemos a permissão do _Prof. Dr. Lucídio dos Anjos Formiga
Cabral_  (DCC/ CI/ UFPB) para usarmos grande parte das 2 primeiras
aulas de seu curso ``_Introdução à Teoria dos Grafos_'', que
brevemente voltará a ser disponibilizado na Internet. Mas
acrescentamos alguns problemas a resolver e alguns exemplos, e
ocasionalmente mudamos algumas figuras (ou copiamos de fontes tais
como Professora Sílvia Fernanda Martins Brandão da Uber
http://www.uber.com.br/silvia/MATD/, e outras.), omitimos, ou
acrescentamos algumas coisas. Se você quiser ver o assunto mais
explicada e profundamente, não precisará de mais que os livros textos
da ementa da disciplina.

Agradecemos a permissão do _Prof. Dr. Lucídio dos Anjos Formiga Cabral_
(DCC/ CI/ UFPB) para usarmos grande parte das 2 primeiras aulas de seu
curso ``Introdução à Teoria dos Grafos'', que brevemente voltará a ser
disponibilizado na Internet. Mas acrescentamos alguns problemas a
resolver e alguns exemplos, e ocasionalmente mudamos algumas figuras
(ou copiamos de fontes tais como Professora Sílvia Fernanda Martins
Brandão da Uber http://www.uber.com.br/silvia/MATD/, e outras.),
omitimos, ou acrescentamos algumas coisas. Se você quiser ver o
assunto mais explicada e profundamente, não precisará de mais que os
livros textos da ementa da disciplina.

Mas há muitos e bons livros
somente sobre grafos, alguns deles na Internet.
link:http://www.ime.usp.br/\~pf/teoriadosgrafos/texto/TeoriaDosGrafos.pdf[]
(_Uma Introdução Sucinta à Teoria dos Grafos_, Wakabayashi- Kohayakawa-
Feofiloff),
link:http://www.slideshare.net/biancamcdantas/introduo-teoria-dos-grafos[],
link:http://www.ime.usp.br/\~pf/grafos-exercicios[],
link:http://www.utm.edu/departments/math/graph/glossary.html[],
link:http://www.iro.umontreal.ca/~hahn/IFT3545/GTWA.pdf[] (_Graph Theory with
Applications_ - Bondy- Murty). Creditamos alguns dos exemplos e
exercícios ao _Prof. Christopher Strobel_ e ao _Prof. Antônio Alfredo
Ferreira Loureiro_.

====

=== Motivação e Introdução

Por que estudar grafos? Porque são:

* Importante ferramenta matemática com aplicação em diversas
áreas do conhecimento;
* Utilizados na definição e/ou resolução de problemas;
* Existem centenas de problemas computacionais que empregam grafos
com sucesso.

Primeiras motivações na área:


* 1735, o Problema das 7 Pontes de Königsberg (atual Kaliningrad):
(((Problema, 7 pontes de Königsberg)))
Duas ilhas A e D, existentes no rio Pregel em Königsberg (Rússia),
foram ligadas às margens do rio (B e C) através de 7 pontes. Pergunta:
é possível iniciar uma caminhada a partir de um dos blocos de terra
(A, B, C ou D), passar por cada uma das pontes exatamente uma vez, e
voltar ao ponto de partida sem nadar pelo rio?

[width="100%",cols="^,^",frame="none",grid="none"]
|====
2+|Você tem que passar por cada de *a,b,c,d,e,f,g* exatamente uma vez.
|image:images/cap4/img01.eps[width="130"]

Situação real -- o problema

|image:images/cap4/img02.eps[width="100"]

Modelo do problema
|====

Resolvido pelo estudo da paridade dos nós: O problema não tem
solução porque tem vértices com paridade ímpar (os termos serão
definidos mais adiante, mas adiantamos que isto significa que há
vértices com número ímpar de arcos incidentes).

* 1847: G.R.Kirchnoff desenvolveu a teoria de árvores para trabalhar
com aplicações em circuitos elétricos.
* 1852: F. Guthrie apresentou informalmente o problema das 4 cores:
São apenas 4 cores suficientes para colorir qualquer mapa em
superfície plana (fronteiras entre regiões têm que ser linhas contínuas com
comprimento maior que 0: não podem ser apenas um ponto), de maneira
que regiões fronteiriças recebam cores distintas? (Isto só
conseguiu ser (aos poucos) provado em a partir de 1976).
* 1859: Sir W.R. Hamilton inventou um jogo que consistia em um
dodecaedro com 12 faces e 20 vértices, com cada face sendo um
pentágono regular e três arestas se encontrando em cada vértice e
os vértices foram rotulados com nomes de 20 cidades importantes. O
objetivo do jogo é achar uma rota pelas arestas do dodecaedro
passando por cada vértice apenas uma vez. (A solução para este
problema específico é fácil de se obter. No entanto, ainda não se
tem uma condição necessária e suficiente para se verificar a
existência de um ciclo hamiltoniano (definição mais adiante) em um
grafo arbitrário.)
* Depois desta época pouca coisa foi investigada em Teoria dos
Grafos por quase um século.
* O interesse ressurgiu na década de 1920 com os estudos de D. König
que se transformaram em um livro, publicado em 1936.

.Problema das (três) Utilidades
[NOTE]
====
[width="100%", cols="^.^a,<.^", frame="none",grid="none"]
|====
| G          E          W



 A          B          C
|Considere 3 casas (A,B,C), cada uma com três utilidades: água (W),
gás (G) e eletricidade (E). As utilidades estão conectadas às
casas por meio de fios e canos. Considerando que todos os fios e
canos estão no mesmo plano, é possível fazer as instalações sem
cruzá-los?

A resposta é *não* (a prova disso é difícil demais para esta
disciplina).
|====
====

=== Conceitos Básicos de Grafos e Digrafos

Um *((grafo))* latexmath:[$G$] é um objeto matemático constituído por
um par latexmath:[$(V,E)$], onde latexmath:[$V$] é um conjunto de
elementos chamados de *((vértices))* (ou *nodos*) (que modelam locais ou
estados ou tempos ou entidades, de problemas reais) e latexmath:[$E$]
é um conjunto de elementos chamados de *((arestas))* (ou *arcos*), cada
aresta latexmath:[$e_k$] modelando a relação de um vértice
latexmath:[$v_i$] para um vértice latexmath:[$v_j$], ditos
*extremos* de latexmath:[$e_k$]. Os vértices extremos de uma aresta
são ditos incidentes nela, e as arestas que se ligam a um vértice
são ditas *incidentes* nele. Dois vértices que são incidentes a
uma (i.é, estão ligados a uma) mesma aresta são ditos *((vértices adjacentes))*.
Duas arestas que são incidentes a um mesmo vértice
são ditas *((arestas adjacentes))*.

.{zwsp}
====
[width="100%", cols="^.^,<.^", frame="none",grid="none"]
|====
|image:images/cap4/img03.eps[width="100"]
|latexmath:[$G = (V,E)$]                               (grafo)

latexmath:[$V = {1, 2, 3, 4, 5, 7}$]               (vértices)

latexmath:[$E = {a, b, c, d, e, f}$]                (arcos)

5,7 são os extremos da aresta latexmath:[$a$].

5,7 são incidentes na aresta latexmath:[$a$];    latexmath:[$a,d$]
são incidentes no vértice 5.

latexmath:[$a,d$] são arestas adjacentes;    5,7 são vértices
adjacentes.
|====
====

.{zwsp}
[NOTE]
====

[[fig_multigrafo]]
.Grafo multigrafo
image::images/cap4/img04.eps[scaledwidth="30%"]

* Um grafo latexmath:[$G = (V, E)$] (<<fig_multigrafo>>) é um
  *((multigrafo))* se existem mais de uma aresta ligando o mesmo par
  de vértices.
* Uma aresta do tipo latexmath:[${v_i,v_i}$] é denominada auto-laço.
* Arestas que possuem os mesmos vértices extremos latexmath:[$v_i
  \not= v_j$] são ditas paralelas ou múltiplas.
* Um grafo (como o anterior) sem auto-laços nem arestas paralelas é
  denominado *grafo simples*.

====


* O número de vértices de um grafo G é denotado por latexmath:[$n =
  |V|$]. O valor latexmath:[$n$] também é conhecido como ordem do
  grafo. (No multigrafo acima, é 4.)
* O número de arestas de um grafo é denotado por latexmath:[$m =
  |E|$]. (No multigrafo acima, é 6.)
* Se latexmath:[$|V|$] e latexmath:[$|E|$] são finitos, o grafo
  latexmath:[$G = (V,E)$] é finito. Caso contrário, é dito infinito.
  Estudaremos apenas grafos finitos.


* O número de arestas incidentes a um vértice latexmath:[$v$] é
  denominado *grau* (latexmath:[$v$]) (ou *valência*) e representado
  por latexmath:[$d(v)$]. (No multigrafo acima, latexmath:[$d(4) =
  5$].) O grau de um vértice isolado é 0.
* latexmath:[$\delta(G)$] é o *grau mínimo* de latexmath:[$G$], o grau
  do vértice de menor grau. (No multigrafo acima, é 2, correspondente
  aos vértices 2 e 3.)
* latexmath:[$\Delta(G)$] é o *grau máximo* de latexmath:[$G$], o grau
  do vértice de maior grau. (No multigrafo acima, é 5, correspondente
  ao vértices 4.)

* *((Vértice isolado))* é o vértice que não possui arestas incidentes
(tem grau 0).
* *((Vértice folha))* (nomenclatura melhor que ((vértice terminal))) é o
vértice que possui grau 1 (Em um digrafo será grau de entrada 1 e
grau de saída 0).
* *((Vizinhos))* de um vértice são os vértices adjacentes a ele. (No
grafo acima, 3 e 4 são vizinhos.)
* Pares de vértices (ou de arestas) não adjacentes são denominadas
*independentes*. (No grafo acima, qualquer uma das arestas de 3 para
4, e a aresta de 1 para 2, são independentes entre si.)
* Um conjunto de vértices (ou arestas) é *independente* se nenhum
par de seus elementos é adjacente.

Teorema:: Seja G = (V,E) um grafo simples com n vértices e m
arestas. Então latexmath:[$\sum_{v \in V}{d(V)} = 2m$].
+
--
[NOTE]
====
Esta fórmula equivale a dizer que a soma dos graus de todos os
vértices é o dobro do número de arestas.
====
--

Prova::
Cada aresta latexmath:[$a$] é incidente em dois vértices latexmath:[$u$] e
latexmath:[$v$], sendo contabilizada no cômputo do grau de
latexmath:[$u$] e também de latexmath:[$v$].

* *((Auto-laço))* é uma aresta com extremos idênticos
latexmath:[$(u,u)$]. *Link* é uma aresta com extremos diferentes
latexmath:[$v_i \not= v_j$]. Portanto, arestas múltiplas são links
com mesmos extremos:
* Um grafo é *simples* se não possuir auto-laço nem arestas
múltiplas.

* (((Grafo, completo))) *Grafo completo* de latexmath:[$n$] vértices (também chamado de
*n-clique*) é um grafo simples em que cada um dos seus
latexmath:[$n$] vértices se liga por 1 aresta a todos os outros
latexmath:[$n-1$] vértices, cada vértice tendo grau
latexmath:[$n-1$], o grafo abaixo é um 5-clique.
Há n nodos, cada um deles incidente em latexmath:[$n-1$] arcos, mas assim cada arco
é contado 2 vezes, portanto o número total de arcos é
latexmath:[$n(n-1)/2$].


.Grafo 5-clique. Pois cada um dos 5 vértices se liga a todos os outros.
image::images/cap4/img05.eps[scaledwidth="30%"]

* (((Grafo,vazio))) *Grafo vazio* é um grafo sem arestas.

=== Classes especiais de grafos

==== Grafo trivial

(((Grafo, trivial)))

*Grafo trivial* é um grafo com apenas um vértice.

==== Grafo bipartido

(((Grafo, bipartido)))

*Grafo bipartido* é aquele em que o conjunto de vértices pode ser
particionado em dois subconjuntos latexmath:[$X$] e latexmath:[$Y$],
tal que cada aresta do grafo tem um extremo em latexmath:[$X$] e o
outro em latexmath:[$Y$]. Isso implica que não há ciclos de
comprimento ímpar. Na <<fig_grafo_bipartido>>, latexmath:[$X$] é o
conjunto dos vértices na parte superior do grafo e latexmath:[$Y$] é o
conjunto na parte inferior.

===== Grafo bipartido completo

(((Grafo, bipartido completo)))

*Grafo bipartido completo* é um grafo bipartido com bipartição
latexmath:[$(X, Y)$] em que cada vértice de latexmath:[$X$] é
adjacente a cada um de todos os vértices de latexmath:[$Y$].
(<<fig_grafo_bipartido>>). Se chamarmos latexmath:[$|X|$] de
latexmath:[$m$] e latexmath:[$|Y|$] de latexmath:[$n$], então
denotamos tal grafo por latexmath:[$K_{m,n}$].

[[fig_grafo_bipartido]]
.Grafo bipartido completo latexmath:[$K_{4,5}$].
image::images/cap4/img06.eps[scaledwidth="25%"]

==== Grafo k-partido

(((Grafo, k-partido)))

*Grafo k-partido* latexmath:[$G(V,E)$] é um grafo cujos vértices podem
ser particionados em k conjuntos (como temos uma partição, esses
conjuntos são disjuntos e união deles é V) de modo que nunca ocorra
que dois vértices do mesmo conjunto sejam ligados por alguma aresta.

==== Grafo regular

(((Grafo, regular)))

*Grafo regular* é aquele em que todos os vértices têm mesmo grau. Se o
grau for latexmath:[$k$], chamamos o grafo de k-regular.  (Exemplo: o
grafo bipartido completo, acima, é 4-regular)

==== Grafo rotulado

(((Grafo, rotulado)))

*Grafo rotulado* em vértices (ou arestas) é aquele em que cada vértice
(ou aresta) é atribuído um rótulo tal como Brasília (ou Ponte da
Amizade) que será seu nome. (Exemplo: o primeiro grafo desta seção é
rotulado nos vértices (1, 2, etc.), e também é rotulado nas arestas
(latexmath:[$a, b,$] etc.))

==== Grafo valorado

(((Grafo, valorado))) (((Grafo, ponderado)))

*Grafo valorado* (ou ponderado) é aquele em que cada aresta (ou
vértice) tem um número real associado a ele, representando um custo ou
ganho em se passar por ele. Exemplos nas definições de problema do
caminho mais curto (<<fig_caminho_mais_curto>>) e da árvore geradora
mínima (<<fig_arvore_geradora>>).

==== Grafo altamente irregular

(((Grafo, altamente irregular)))

*Grafo altamente irregular* é aquele em que cada um de seus vértices é
adjacente a vértices de graus diferentes entre si.

==== Grafo complementar

(((Grafo, complementar)))

Dado um grafo latexmath:[$G$], seu grafo *complementar*
latexmath:[$\bar{G} $] é o grafo que contém as arestas que teria se
fosse completo, mas que não estão em latexmath:[$G$].

.Grafos complementares. Os grafos cinza e preto são complementares entre si.
image::images/cap4/img07.eps[scaledwidth="60%"]

.Note que:
[NOTE]
====
* O complementar de um grafo sem arestas é um grafo completo e vice
  versa.
* Um conjunto de vértices independentes em um grafo corresponde a um
  clique no grafo complementar e vice versa.

====

==== Grafo conexo

(((Grafo, conexo)))

Um grafo é dito *conexo* se houver um caminho entre quaisquer dois
de seus vértices.

.Grafo conexo
image::images/cap4/img08.eps[scaledwidth="30%"]

==== Grafo desconexo

(((Grafo, desconexo)))

Um grafo é dito *desconexo* se não houver um caminho entre quaisquer dois de
seus vértices.

.Grafo desconexo. Note que não há caminho entre X~2~ e X~5~.
image::images/cap4/img09.eps[scaledwidth="30%"]

Um grafo desconexo é formado por pelo menos dois subgrafos conexos,
disjuntos em relação aos vértices. Cada um destes subgrafos
conexos é dito ser uma *componente conexa* do grafo.

image::images/cap4/img10.eps[scaledwidth="30%"]


Um vértice é chamado de um *((vértice de corte))* se sua remoção
(juntamente com as arestas a ele conectadas) aumenta o número de
componentes conexas (ver definição acima) do grafo. Isto é, a remoção
de um vértice de corte faz com que um [sub] grafo que era conexo fique
dividido em dois ou mais (sub-) subgrafos, cada um conexo em relação a
si mesmo, mas sem ligação de um para os outros. Exemplo: o vértice 4
na definição de multigrafo, acima.

Uma aresta é chamada de *((aresta ponte))* (também conhecida por
*((aresta de corte))* ou *istmo*) se sua remoção aumenta o número de
componentes conexas (ver definição acima) do grafo. Exemplo: a aresta
latexmath:[$x_1 x_2$] na definição de grafo desconexo, acima.

Dois grafos latexmath:[$G$] e latexmath:[$H$] são *idênticos* se:

* latexmath:[$V(G) = V(H)$];
* latexmath:[$E(G) = E(H)$];
+
--
[NOTE]
====

- A cada arco de latexmath:[$G$] ligando os vértices latexmath:[$u,v$] corresponde um arco
de mesmo nome ligando os vértices latexmath:[$u,v$] em latexmath:[$H$]; e vice-versa)

- latexmath:[$(u,v) \in E(G)     \leftrightarrow    (u,v) \in
E(H)$]

====
--

Grafos idênticos podem estar _((graficamente distorcidos))_ e não ser
muito fácil de você olhar para eles e logo perceber que são
idênticos. Mas ambos podem ser representados por um mesmo diagrama.
(Exemplo: os dois grafos abaixo, se já tivéssemos mudado os
rótulos dos vértices do segundo grafo de 1,2,3,4,5,6,7,8 para
a,h,d,i,g,b,j,c, respectivamente.)

Um *isomorfismo* (denotado latexmath:[$G \approx H$]) entre dois
grafos latexmath:[$(G,H)$] é uma bijeção latexmath:[$f$] de
latexmath:[$V(G)$] em latexmath:[$V(H)$] tal que

[latexmath]
++++
\[(u,v) \in E(G)      \leftrightarrow      (f(u),f(v)) \in E(H) \]
++++

isto é, para quaisquer dois vértices latexmath:[$u$] e
latexmath:[$v$] de latexmath:[$G$], eles são adjacentes em
latexmath:[$G$] se e somente se latexmath:[$f(u)$] e
latexmath:[$f(v)$] são adjacentes em latexmath:[$H$]. Dois digrafos
são *isomórficos* (definição adiante) se existe um isomorfismo entre os grafos a eles
equivalentes e se é preservada a ordem dos vértices de cada arco.

[width="100%",cols="^.^1,^.^2,^.^2",frame="none",grid="none",options="header"]
|====
|Grafo latexmath:[$G$]	|Grafo latexmath:[$H$] |Um isomorfismo entre
latexmath:[$G$] e latexmath:[$H$]
|image:images/cap4/img11.eps[width="60"]
|image:images/cap4/img12.eps[width="130"]
|latexmath:[$f(a) = 1$]

latexmath:[$f(b) = 6$]

latexmath:[$f(c) = 8$]

latexmath:[$f(d) = 3$]

latexmath:[$f(g) = 5$]

latexmath:[$f(h) = 2$]

latexmath:[$f(i) = 4$]

latexmath:[$f(j) = 7$]
|====

Compare esta definição com a de grafos idênticos. Obviamente,
grafos idênticos são isomórficos. No entanto, o reverso não é
verdade. (No exemplo acima, é possível alterar o nome dos vértices
do grafo H de forma que este fique idêntico a latexmath:[$G$], mas
isso nem sempre é possível. Exemplo: grafo latexmath:[$G =
\{(1,2),(1,3),(1,4),(2,3)\}$] e grafo latexmath:[$H =
\{(1,2),(1,3),(2,3),(3,4)\}$]. Desenhe os diagramas dos dois grafos,
depois explique porque são isomórficos, e porque não são idênticos.)

O isomorfismo de grafos preserva as propriedades:

* Simetria: latexmath:[$G \approx H    \leftrightarrow     H \approx
G$]
* Reflexividade: latexmath:[$G \approx G$]
* Transitividade: latexmath:[$(G \approx H) \wedge (H \approx I)
\leftrightarrow    (G \approx I)$]

Se latexmath:[$G \approx H$], valem as seguintes proposições:

* G e H têm o mesmo número de vértices
* G e H têm o mesmo número de arestas
* G e H têm a mesma sequência de graus (a sequência de graus de um
  grafo é a ordenação não crescente dos graus de seus vértices)

==== Digrafo ou grafo direcionado

(((Digrafo))) (((Grafo, direcionado)))

*Grafo direcionado* ou *digrafo* é aquele que tem todas as suas
arestas direcionadas. Prefere-se chamar de arcos as arestas
direcionadas, e de A o conjunto desses arcos. Cada arco é representado
por um par ordenado, onde o primeiro elemento é a origem do arco e
segundo é seu final. No exemplo abaixo,

latexmath:[$G = (V,A)$] +
latexmath:[$V = \{2,3,5,7,8,9,10,11\}$] +
latexmath:[$A = \{(3,8), (3,10), (5,11), (7,8), (7,11), (8,9),
(11,2), (11,9), (11,10)\}$].

NOTE: Pronuncia-se di-**GRA**-fo, pois não há acento. Alguns descuidados
escrevem  e pronunciam como ``dígrafo'', com acento, o que é erro pois
corresponde ao conceito ``duas letras com apenas um só fonema, como ss
entre duas vogais'', enquanto ``digrafo'' é aportuguesamento do inglês
``digraph'' (``directed graph'', ``grafo direcionado'').

===== Digrafo simples

(((Digrafo, simples)))

* *Digrafo simples* é um digrafo que não tem auto-laços e os arcos
são todos distintos. (Exemplo acima.)

(((Digrafo, acíclico)))

* Digrafo simples *acíclico* é um digrafo simples que não tem
ciclos. (Exemplo acima.)
* O grafo latexmath:[$G$] obtido removendo-se as orientações dos
arcos de um digrafo latexmath:[$D$] é chamado de grafo equivalente a
latexmath:[$D$]. Se latexmath:[$D$] for simples, latexmath:[$G$] pode
não o ser. (Você mesmo ache um exemplo disso.)

Cada vértice latexmath:[$v$] de um digrafo latexmath:[$(V,A)$] tem
um grau de entrada latexmath:[$grauent(v)$] ou
latexmath:[$grau^{+}(v)$](que é o número de arcos que chegam nele)
e um grau de saída latexmath:[$grausai(v)$] ou
latexmath:[$grau^{-}(v)$] (que é o número de arcos que saem dele),
onde:

[latexmath]
++++
\[\sum{grauent(v_i)} = \sum{grausai(v_i)} = |A|\]
++++

Prova:: Cada arco latexmath:[$a$] sai de um nodo latexmath:[$u$] entra
num nodo latexmath:[$v$], sendo contabilizada no cômputo do grau de saída
de latexmath:[$u$] e também no grau de entrada de latexmath:[$v$].

===== Digrafo fracamente e fortemente conectado

(((Digrafo, fracamente conectado)))
(((Digrafo, fortemente conectado)))

Um digrafo latexmath:[$D$] é chamado de *fracamente conectado* (ou
apenas *conectado*) se o grafo equivalente é um grafo conexo. Um
digrafo é *fortemente conectado* ou *forte* se ele tem um caminho
orientado de latexmath:[$u$] a latexmath:[$v$] e um caminho orientado
de latexmath:[$v$] a latexmath:[$u$] para cada par de vértices
latexmath:[$u,v$].

==== Subgrafo

(((Subgrafo)))

* Um grafo latexmath:[$H$] é um *subgrafo* de latexmath:[$G$]
(latexmath:[$H \subseteq G$]) se latexmath:[$V(H) \subseteq V(G)$] e
latexmath:[$E(H)\subset E(G)$].
* Quando latexmath:[$H \subseteq G$] e latexmath:[$H \not= G$],
denotamos latexmath:[$H \subseteq G$] e dizemos que latexmath:[$H$]
é *subgrafo próprio* de latexmath:[$G$].Se latexmath:[$H$] é um
subgrafo de latexmath:[$G$] então latexmath:[$G$] é um *supergrafo*
de latexmath:[$H$]
* Um *subgrafo gerador* de latexmath:[$G$] é um subgrafo
latexmath:[$H$] com latexmath:[$V(H) = V(G)$]

* Seja latexmath:[${V}'$] um subconjunto não vazio de
latexmath:[$V$]. O subgrafo de latexmath:[$G$] cujo conjunto de
vértices é latexmath:[${V}'$] e o conjunto de arestas é o conjunto
de todas as arestas de latexmath:[$G$] com ambos extremos em
latexmath:[${V}'$], é chamado de *subgrafo de latexmath:[$G$]
induzido pelo conjunto de vértices latexmath:[${V}'$] *. Denotamos
por latexmath:[$G[{V}'\]$] o subgrafo induzido de latexmath:[$G$] por
latexmath:[${V}'$].

* Seja latexmath:[${E}'$] um subconjunto não vazio de arestas de
latexmath:[$E$]. O subgrafo de latexmath:[$G$] cujo conjunto de
vértices é o conjunto dos extremos das arestas em
latexmath:[${E}'$] é chamado de *subgrafo de latexmath:[$G$]
induzido pelo conjunto de arestas latexmath:[${E}'$]*.

* latexmath:[$G[V \setminus {V}'\]$], também denotado por
  latexmath:[$G-{V}'$] , é o subgrafo obtido a partir de
  latexmath:[$G$] pela remoção dos seus vértices latexmath:[$v$] que
  também estão em latexmath:[${V}'$], e remoção de toda aresta incidente
  em algum desses latexmath:[$v$].
* latexmath:[$G-{E}'$] é o subgrafo gerador de latexmath:[$G$] com
  conjunto de arestas latexmath:[$E \setminus {E}'$].
* latexmath:[$G+{E}'$] é o grafo obtido a partir de latexmath:[$G$]
  adicionando um conjunto de arestas latexmath:[${E}'$].
* Sejam os subgrafos latexmath:[$G_1, G_2 \subseteq G$].
  latexmath:[$G_1$] e latexmath:[$G_2$] são *disjuntos (em vértices)*
  se latexmath:[$V(G_1) \cap V(G_2) = \emptyset$]. E são *disjuntos
  (em arestas)* se latexmath:[$E(G_1) \cap E(G_2) = \emptyset$].


==== Exercício de fixação

Reestude com rigor todas as definições
e teoremas acima, entendendo e memorizando, depois feche o livro e
responda as seguintes perguntas, anotando as respostas para as
conferir somente ao final de todo o exercício:


.. Utilizando a <<fig_caminho_mais_curto>> responda:
  1) Quais são os vértices? 2) E as arestas?  3) Quais os extremos da
  aresta de maior peso? 4) Que vértices incidem nessa aresta? 5) Que
  vértices são adjacentes via essa aresta? 6) Que arestas incidem no
  vértice latexmath:[$A$]? 7) Que arestas são adjacentes via esse
  vértice? 8) Este é um multigrafo? 9) Tem algum auto-laço? 10) Tem
  arestas paralelas? 11) É um grafo simples? 12) É finito? 13) Qual é
  a ordem do grafo?  14) Qual o grau do vértice latexmath:[$A$]? 15)
  Qual o grau mínimo de latexmath:[$G$]? 16) Qual o grau máximo de
  latexmath:[$G$]? 17) Há algum vértice isolado? 18) Há algum vértice
  folha?  19) Quais são os vizinhos do vértice latexmath:[$A$]?  20)
  Os vértices latexmath:[$A$] e latexmath:[$D$] são independentes ou
  vizinhos? 21) As arestas de maior e de menor peso são independentes
  ou adjacentes?  22) Sendo este um grafo simples, vale o teorema que
  diz que a soma dos graus dos vértices é o dobro do número das
  arestas?
+
--

Respostas:: 01) Quais são os vértices? A,B,...,G. 02) E as arestas?
AB, AD, BC, BE, BD, CE, DE, DF, EF, EG. 03) Qual a aresta de maior
peso?  DE, com peso 15. 04) Que vértices incidem nessa aresta? D e E.
05) Que vértices são adjacentes via essa aresta? D e E. 06) Que
arestas incidem no vértice A? AB e AD. 07) Que arestas são adjacentes
via esse vértice? AB e AD. 08) Este é um multigrafo? Não. 09) Tem
algum auto-laço? Não. 10) Tem arestas paralelas? Não. 11) É um grafo
simples? Sim, pois não possui auto-laço. 12) É finito? Sim. 13) Qual é
a ordem do grafo? Sim. 14) Qual o grau do vértice A? 7, pois tem 7
vértices. 15) Qual o grau mínimo de G? 2, pois A,C,G têm grau 2, e
nenhum outro vértice tem grau menor. 16) Qual o grau máximo de G? 5,
pois E tem grau 5 e nenhum outro vértice tem grau maior. 17) Há algum
vértice isolado? Não, todos os vértices incide em alguma aresta. 18)
Há algum vértice folha? Não, pois nenhum os vértices tem grau 1 19)
Quais são os vizinhos do vértice A? B e D. 20) Os vértices A e D são
independentes ou vizinhos? Vizinhos. 21) As arestas de maior e de
menor peso são independentes ou adjacentes? A aresta (DE) de maior
peso (15) e a aresta (AD) (também poderia ser CE) de menor peso são
adjacentes através do vértice D (também poderia ser o vértice E). 22)
Sendo este um grafo simples, vale o teorema que diz que a soma dos
graus dos vértices é o dobro do número das arestas? Sim. Conferindo:
22 = 2 x 11.

--

.. Desenhe um grafo completo com 6 nodos e verifique se o número de
  arcos é latexmath:[$6 \cdot (6-1)/2 = 15$] Desenhe um grafo
  4-partido.  Desenhe um grafo 2-regular com 6 vértices. Desenhe um
  grafo conexo.  Desenhe um grafo com 2 partições desconexas. Insira
  um vértice no grafo acima, depois acrescente o menor número de
  arestas que o torne conexo. Aponte um vértice de corte e uma aresta
  ponte, no grafo modificado.
.. Dê exemplo de dois grafos idênticos, mas um pouco difíceis de
  reconhecer isto à primeira vista.
.. Desenhe 2 grafos não idênticos mas isomórficos, depois prove que
  realmente são isomórficos.
.. Dê exemplo de um digrafo que seja cíclico, outro que seja acíclico.
.. Dê exemplo de um digrafo conexo, outro de um desconexo. Escreva a
  matriz de adjacência e a lista de adjacência para o digrafo
  desconexo.
.. Elabore um grafo de 7 vértices e divida-o em dois:
   latexmath:[$G$] (com 4 vértices) e latexmath:[$H$] (com 3 vértices)
   podendo haver uma pequena interseção entre eles. Agora, ache
   latexmath:[$G-H$].

=== Percursos em Grafos em Geral e em Cliques

==== Passeio

((Passseio)):: Um *passeio* (_walk_) ligando o vértice v~1~ ao vértice v~k~ de um
  grafo é uma sequência de arcos contíguos (cada arco começa no
  vértice onde o anterior terminou), de modo que a sequência começa em
  v~1~ e termina em v~k~. Tal sequência de arcos pode ser escrita
  somente como uma sequência dos nomes dos vértices, por exemplo
  v~1~v~2~v~3~ ... v~k~; ou como uma sequência somente das
  representações dos arcos como pares de vértices, por exemplo
  (v~1~v~2~), (v~2~v~3~), ..., (v~i~v~i+1~), (v~i+1~v~i+2~),  ...,
  (v~k-1~v~k~); ou como uma sequência somente dos nomes dos arcos, por
  exemplo abcde; ou como uma sequência intercalando nomes de vértices
  e nomes de arcos, como em AcCgDfB. (Note que não se proibiu passar
  mais de 1 vez pelo mesmo vértice). (Exemplo no grafo das 7 pontes de
  Königsberg: AcCdAbBbAeD é um passeio desde A até D).

==== Passeio elementar

((Passeio elementar)):: Um passeio é dito *elementar* se não passar
duas vezes pelo mesmo vértice. O grafo
latexmath:[$AcCgDfB$] é um passeio elementar desde latexmath:[$A$] até
latexmath:[$B$].

==== Passeio simples

((Passeio Simples)):: Um passeio é dito simples se não passa mais que 1 vez em
nenhum vértice ou aresta.

==== Trilha

((Trilha)):: Um passeio é chamado de trilha se não passa duas vezes
pela mesma aresta. No grafo: _AaBfDeAcCgD_ é uma trilha desde
latexmath:[$A$] até latexmath:[$D$]. Note que passou 2 vezes pelos
vértices latexmath:[$A e D$], mas não passou nenhuma duas vezes por
nenhuma aresta.

==== Ciclo

((Ciclo)):: Um *ciclo* é um passeio simples e fechado (o vértice
inicial é o mesmo que o vértice final). (Exemplo no mesmo grafo:
_AcCdAbBbA_ é um ciclo desde latexmath:[$A$] até
latexmath:[$A$].)

==== Caminho no Digrafo

((Caminho no Digrafo)):: Em um digrafo, um *((caminho))* é um passeio
no qual todos os arcos possuem a mesma orientação. (Exemplo no
diagrama da definição de digrafo: 5, arco, 11, arco, 10) Um caminho
não repete vértices nem arcos. Em um grafo não direcionado, a relação
caminho é uma equivalência, pois é reflexiva (caminho(u,u)), simétrica
(caminho(u,v) ssse caminho(v,u)) e transitiva (caminho(x,y) e
caminho(y,z) implicam caminho(x,z)).

==== Circuito no Digrafo

Circuito no Digrafo:: Em um digrafo, um *((circuito))* (ou ciclo
direcionado simples) é um caminho simples (isto é, sem subcircuitos
dentro dele) e fechado, retornando a qualquer vértice por onde o
comecemos. (Exemplo: na <<fig_circuito>>, um circuito passará pelos
vértices 1,2,4,3 e voltará ao vértice 1, sempre seguindo os arcos na
direção correta.)

[[fig_circuito]]
.Digrafo com um circuito
image::images/cap4/img14.eps[scaledwidth="30%"]

==== Grafo euleriano

Grafo euleriano:: Um grafo conectado _G(V,A)_ é dito ser
((*euleriano*)) se existe uma _trilha_ (nela, cada aresta está
presente e ocorre exatamente 1 vez) fechada (isto é, que volta ao
ponto de partida).
+
** *Exemplo 1:* Cada vértice do grafo (na <<fig_euleriano>>)
tem um grau par, portanto este é um grafo euleriano; realmente,
seguindo as arestas em ordem alfabética obtém-se um circuito/ciclo
euleriano.

** *Exemplo 2:* No clique latexmath:[$k5$] do Teorema de Ore
(<<fig_ore>>), se numerarmos os vértices como 1,2,3,4,5 no sentido dos
ponteiros do relógio, o ciclo euleriano será 1,2,3,4,5,1,3,5,2,4,1.)

[[fig_euleriano]]
.Grafo euleriano
image::images/cap4/img15.eps[scaledwidth="40%"]

===== Grafo semi-euleriano

Grafo semi-euleriano::
Um grafo conectado e não-euleriano, _G_, é semi-euleriano se existe
uma trilha que usa cada aresta de _G_ exatamente 1 vez (com isso, terá
passado em todos os vértices pelo menos 1 vez, sem precisar fechar o
circuito). No grafo da <<fig_semi_euleriano>>, se seguirmos as arestas
na ordem _1,2,3,4,5,6,7_, teremos passado por todas as arestas
exatamente 1 vez, portanto o grafo é *semi-euleriano*. Mas não fizemos
um passeio simples, pois passamos mais de 1 vez em alguns vértices.
Note que o grafo não é euleriano, pois tem vértices de grau ímpar.

[[fig_semi_euleriano]]
.Grafo semi-euleriano
image::images/cap4/img16.eps[scaledwidth="40%"]

===== Teorema de Euler

Teorema (Euler 1736) (pronuncie como ``Óilêr'')::  Um grafo
conectado latexmath:[$G$] é euleriano se e somente se o grau de cada
um de seus vértices é par.
Corolário::: Um grafo conectado latexmath:[$G$] é euleriano se e
somente se ele pode ser decomposto em ciclos.
Corolário II::: Um grafo conectado latexmath:[$G$] é semi-euleriano
se e somente se ele possui exatamente 2 vértices de grau ímpar.

Outra apresentação dos Teoremas de Euler::

Teorema de Euler 1:::
- Se um grafo tem quaisquer vértices de grau ímpar, então ele não pode
  ter um Circuito de Euler.
- Se um grafo é conexo e cada vértice tem grau par, então ele tem pelo
  menos um Circuito de Euler (usualmente, mais).

Teorema de Euler 2:::
- Se um grafo tem mais de 2 vértices de grau ímpar, então ele não pode
  ter uma Trilha de Euler.
- Se o grafo é conexo e tem exatamente dois vértices de grau ímpar,
  então ele tem pelo menos uma Trilha de Euler (usualmente, mais). Tal
  trilha deve começar em um dos vértices de grau ímpar e terminar no
  outro.

Teorema de Euler 3:::
- A soma dos graus de todos os vértices de um grafo é um número par
  (exatamente o dobro do número de arestas).
- Em cada grafo, o número de vértices de grau ímpar tem que ser par.


[width="100%",cols="^1,^2,^3",frame="topbot",options="header,footer"]
|====
|Número de vértices de grau IMPAR em G
|Número de Circuitos de Euler
|Número de Trilhas de Euler (passando por vértices de todos os vértices)
| 0 | ≥1 | ≥ 1 (pois um circuito também é uma trilha)
| 1 | Condição impossível | Condição impossível
| 2 | 0 | ≥ 1 (começam em um vértice de grau ímpar, terminam no outro)
| ≥2  | 0|0
|====

==== Grafo hamiltoniano

Grafo hamiltoniano::
+
--

Um grafo latexmath:[$G(V,A)$] é dito ser hamiltoniano se existe um
ciclo que passa exatamente uma vez em cada um dos vértices de
latexmath:[$G$]. (O ciclo é uma sucessão de arestas adjacentes que
visita todos os vértices do grafo uma só vez, sendo o último
vértice visitado adjacente ao primeiro.)

Todo grafo completo (clique) que contém mais de 2 vértices é
hamiltoniano.

.Grafo hamiltoniano
image::images/cap4/img17.eps[scaledwidth="40%"]

--

Teorema::: Um grafo completo de latexmath:[$n$] vértices tem
latexmath:[$(n-1)!/2$] ciclos hamiltonianos.


Prova do Teorema::: Fixe um vértice latexmath:[$v_1$]. O número de
ciclos hamiltonianos começando e terminando nele (por exemplo,
latexmath:[$v_1 v_2 \cdots v_n v_1$]) é o número de permutações
com os latexmath:[$n-1$] outros vértices latexmath:[$\{v_2, \ldots
,v_n\}$], portanto é latexmath:[$(n-1)!$] Mas cada ciclo está sendo
percorrido em 2 sentidos, direto e inverso (e.g.: 1234561 e 1654321),
portanto, corrigindo, há latexmath:[$(n-1)!/2$] ciclos hamiltonianos
começando e terminando em latexmath:[$v_1$]. Mas, por causa da
circularidade (123451 é o mesmo que 234512 que é o mesmo que
3451234 que é o mesmo que ...), todos os ciclos começando e
terminando em qualquer dos outros vértices diferentes de
latexmath:[$v_1$] já estão contados. Portanto, o número de ciclos
hamiltonianos é latexmath:[$(n-1)! / 2$].

===== Grafo semi-hamiltoniano

Grafo Semi-hamiltoniano::
Um grafo latexmath:[$G(V,A)$] é dito ser *semi-hamiltoniano* se não é
hamiltoniano e existe um passeio que passa exatamente uma vez em cada
um dos vértices de latexmath:[$G$].

.Grafo Semi-hamiltoniano
image::images/cap4/img18.eps[scaledwidth="25%"]

Teorema (Dirac 1952):: Uma condição suficiente, mas não
necessária, para que um grafo simples latexmath:[$G$] com
latexmath:[$n (>2)$] vértices seja hamiltoniano é que o grau de
todo vértice de latexmath:[$g$] seja latexmath:[$\geq n/2$].

image::images/cap4/img19.eps[scaledwidth="40%"]

===== Teorema de Ore

Teorema (Ore 1960):: Uma condição suficiente, mas não necessária,
para que um grafo simples latexmath:[$G$] com latexmath:[$n (>2)$]
vértices seja hamiltoniano é que a soma dos graus de cada par de
vértices não adjacentes seja no mínimo latexmath:[$n$].

Exemplo::: A condição é satisfeita no clique latexmath:[$k5$]
(<<fig_ore>>).  E, se numerarmos os vértices como 1,2,3,4,5 no sentido
dos ponteiros do relógio, o ciclo será 1,2,3,4,5,1.

[[fig_ore]]
.Grafo ilustrando o Teorema de Ore
image::images/cap4/img20.eps[scaledwidth="40%"]

[[problema_caminho_mais_curto]]
==== Problema do caminho mais curto

O problema do caminho mais curto consiste na minimização do custo
total de travessia de um grafo ponderado (com custos associados a
cada aresta) desde um vértice origem até um vértice destino. Se
for oferecida como optativa a disciplina Análise (da complexidade) e
Projeto de Algoritmos (do Bacharelado em Ciência da Computação, da
UFPB), você poderá aprender e implementar algoritmos (tais como o
de Dijkstra e o de Bellman-Ford) que resolvem o problema de forma
muito eficiente.

Exemplo::: Na <<fig_caminho_mais_curto>>, o caminho de custo mínimo
entre latexmath:[$D$] e latexmath:[$E$] não é latexmath:[$D-E$], mas
sim latexmath:[$D-F-E$], com uma custo total de latexmath:[$6+8 = 14$].

[[fig_caminho_mais_curto]]
.Exemplo de grafo para cálculo do caminho mais curto
image::images/cap4/img21.eps[scaledwidth="35%"]

==== Problema do carteiro chinês

O problema do carteiro chinês consiste em encontrar um caminho
mais curto ou um circuito fechado que, pelo menos uma vez, visite
cada aresta de um grafo conectado. (Sim, quando o grafo possui um
circuito euleriano (um passeio fechado que abrange toda aresta uma
vez), esse circuito é uma solução ótima.)
Exemplo::: Grafo não direcionado. Você tem 4 vértices 1,2,3,4. Os
arcos, não direcionados, têm comprimentos:    latexmath:[$(1,2) =
3;    (1,3) = 12;    (1,4) = 10;    (2,3) = 4;    (3,4) = 5$].
Desenhe o grafo. O carteiro precisa sair do vértice 1 e voltar a ele
no final, passando por cada arco pelo menos 1 vez. Qual o passeio de
menor comprimento total?   (Resposta: passar nos vértices
1,2,3,4,1,2,3,2,1, percorrendo latexmath:[$12+5+10+3+4+4+3 = 41$]
unidades de comprimento).


==== O problema do caixeiro viajante

O problema do caixeiro viajante (TSM = Travelling SalesMan; TSP =
Travelling Sales Person) consiste na procura de um circuito que
possua o menor comprimento total, começando numa cidade qualquer,
entre várias, visitando cada cidade precisamente uma vez e
regressando à cidade inicial. Ver algoritmo aproximado, acima.

=== Árvores e Árvores Geradoras

(((Árvores)))

Um grafo conexo que não contém ciclos é chamado de árvore. Um
grafo que não contém ciclos é uma floresta (portanto, uma floresta
é uma união disjunta de árvores; e corresponde a um grafo
disjunto; note que estamos falando de grafos (não de digrafos),
portanto as arestas não são direcionadas).

Seguindo o costume, chamaremos de nodos aos vértices de uma árvore.
Uma árvore é denominada enraizada se um nodo é escolhido como
especial, passando a ser chamado de raiz da árvore. Uma árvore que
não é enraizada é denominada livre. Os nodos vizinhos à raiz são
chamados de seus filhos ou ramos, e ela chamada de pai deles. Estes
filhos levam a outros nodos que também possuem outros filhos deles,
que os têm por pais. E assim por diante. Os nodos que não possuem
filhos são conhecidos como folhas (nomenclatura melhor que nodos-
terminais). Para cada folha, existe um só caminho entre a raiz e ela.

Teorema:: Num grafo que é uma árvore, toda sua aresta é uma aresta
de corte   (ver definição, acima).

Teorema:: Se latexmath:[$G$] é uma árvore com latexmath:[$n$]
nodos, então latexmath:[$G$] possui latexmath:[$n-1$] arestas.

Teorema:: Se latexmath:[$F$] é uma floresta com latexmath:[$n$]
nodos e latexmath:[$k$] componentes conexos, então latexmath:[$F$]
contém
latexmath:[$n-k$] arestas.

Teorema:: Seja latexmath:[$G$] um grafo de ordem latexmath:[$n$].
latexmath:[$G$] é uma árvore se, e somente se, latexmath:[$G$] é
conexo e contém latexmath:[$n-1$] arestas.

Teorema:: Seja latexmath:[$G$] um grafo de ordem latexmath:[$n$].
latexmath:[$G$] é uma árvore se, e somente se, latexmath:[$G$] não
possui ciclos e contém latexmath:[$n-1$] arestas.

Teorema:: Seja latexmath:[$T$] uma árvore (enraizada) de ordem
latexmath:[$n \geq 2$]. Então latexmath:[$T$] possui no mínimo 1
folha.

==== Árvore Geradora

(((Árvore, Geradora)))

Dado um grafo conexo latexmath:[$G$], podemos sucessivamente remover
uma qualquer aresta que esteja em um ciclo, até que não mais reste
nenhum ciclo. Deste modo, teremos removido o menor número de arestas
(latexmath:[$|E| - |V| + 1$]) necessário para transformar o grafo em
acíclico e, portanto (uma vez que também é conexo), em uma árvore
que contém todos os vértices de latexmath:[$G$] e será chamada de
*árvore geradora* (ou árvore extensora, ou árvore de cobertura) de
latexmath:[$G$]. Muitas árvores diferentes (e não serão
isomórficas) podem ser geradoras de um mesmo grafo. Se o grafo for
ponderado (cada aresta tendo um peso que representa quão
desfavorável ela é), e se atribuirmos um peso à árvore geradora
que seja calculado pela soma dos pesos das arestas que a compõem,
então uma *árvore geradora mínima* (ou de peso total mínimo, ou
de custo mínimo) é uma árvore geradora com peso menor ou igual a
cada uma de todas as outras árvores geradoras possíveis. Qualquer
grafo tem uma *((floresta)) de árvores mínimas*, que é uma união de
árvores geradoras mínimas de cada uma de suas componentes conexas.

[[fig_arvore_geradora]]
.Arvore geradora mínima em negrito
image::images/cap4/img22.eps[scaledwidth="40%"]

Neste grafo, um peso aproximadamente igual ao seu comprimento foi
atribuído a cada aresta. Uma árvore geradora mínima deste grafo
está em negrito.

=== Atividades

NOTE: resolva os exercícios abaixo, sem olhar as respostas. Só
depois compare sua resposta com a deste livro (adaptei a partir de
http://goo.gl/mfvvx2 )

. Utilize o algoritmo de força bruta para resolver o problema do
caixeiro viajante para o grafo das quatro cidades mostradas abaixo.
+
[width="100%", cols="^.^",frame="none",grid="none"]
|====
|image:images/cap4/img23.eps[width="150"]
|====
. Pode um grafo ter um circuito euleriano , mas não um hamiltoniano?
Explique sua resposta.
. Pode um grafo ter um circuito hamiltoniano, mas não um euleriano ?
Explique sua resposta.
. No grafo abaixo, coloque em negrito arestas para indicar um
circuito hamiltoniano.
+
[width="100%", cols="^.^",frame="none",grid="none"]
|====
|image:images/cap4/img26.eps[width="130"]
|====
. Qual é o grau (ou valência) do vértice A no grafo abaixo?
+
--
image::images/cap4/img28.eps[width="150"]
[width="100%", cols="<,<,<,<", frame="none", grid="none"]
|====
|a)	3
|b)	4
|c)	5
|d)	6
|====
--
. Qual das seguintes afirmações sobre um grafo conexo sempre é
verdade?
.. Cada par de vértices é ligado por uma única aresta.
..	Um caminho de arestas existe entre quaisquer dois vértices
do gráfico.
..	Há um número par de vértices do gráfico.
..	Há um número par de arestas no gráfico.
. Qual dos grafos à abaixo tem um circuito euleriano?
+
--
image::images/cap4/img29.eps[scaledwidth="40%"]
.. Grafo I, pois há um número par de arestas em cada um de todos os
seus nodos.
.. Grafo II, pois há um número par de arestas em cada um de todos
os seus nodos.
.. Ambos I e II
.. Nem I nem II
--

. Considere o caminho representado pela sequência de arestas
numerados no gráfico seguinte. Por que o caminho não representa um
circuito de Euler (pronuncie como ``Óilêr'')?
+
--
image::images/cap4/img30.eps[width="160"]

.. O caminho não inicia e para no mesmo vértice.
.. O caminho não cobre todas as bordas do gráfico.
.. O caminho utiliza algumas arestas mais do que uma vez.
.. O caminho não toca cada vértice do gráfico.
--

. Se um gráfico tem 8 vértices de grau (valência) ímpar, qual é
o número mínimo de arestas que têm de ser adicionadas (ou
duplicadas) para que o grafo se transforme num euleriano ?
+
[width="100%", cols="<,<,<,<",frame="none",grid="none"]
|====
|a)	2 |b)	4 |c)	6 |d)	8
|====
. Quais das seguintes sequências de letras descreve um circuito
hamiltoniano para o grafo abaixo?
+
--
image::images/cap4/img31.eps[width="130"]

[width="100%", cols="<,<",frame="none",grid="none"]
|====
|a)	latexmath:[$ABCDEFGA$]
|c)	latexmath:[$ACBFGDEA$]
||
|b)	latexmath:[$ACBAEGFDEA$]
|d)	latexmath:[$ABCDGEF$]
|====
--

. Para o grafo abaixo, qual é o custo do circuito hamiltoniano
obtido usando o algoritmo do vizinho mais próximo (ainda não
visitado), começando por latexmath:[$A$]?
+
--

image::images/cap4/img32.eps[width="160"]

[width="100%", cols="<,<,<,<",frame="none",grid="none"]
|====
|a)	60
|b)	54
|c)	62
|d)	66
|====

--

. Para o problema do caixeiro viajante (TSM ou TSP) (circuito
hamiltoniano) aplicado a seis cidades, quantas tours são possíveis
(e quantas são únicas)?
+
[width="100%", cols="<,<,<,<",frame="none",grid="none"]
|====
|a)	60 possíveis
|b)	120 possíveis
|c)	360 possíveis
|d)	720 possíveis
|====
. Para o grafo abaixo, qual é o custo do circuito hamiltoniano
obtido pelo algoritmo obtido usando o algoritmo das arestas
ordenadas.
+
--

image::images/cap4/img33.eps[width="160"]
[width="100%", cols="<,<,<,<",frame="none",grid="none"]
|====
|a)	220
|b)	225
|c)	235
|d)	295
|====
--

. Um grafo latexmath:[$G$] tem 100 vértices e é formado por duas
componentes conexas, cada uma delas sendo um grafo completo. Qual o
menor número de arestas que latexmath:[$G$] pode ter?

. Um grafo _G_ tem 100 vértices e é formado por duas componentes
  conexas, cada uma delas sendo um grafo completo. Qual o menor número
  de arestas que _G_ pode ter?

=== Soluções

. Caminhos ABCDA e ACBDA têm custo 155.  Caminho ABDCA tem o mínimo
custo, 120.
. Sim. Por exemplo, o grafo abaixo.
+
--
image::images/cap4/img24.eps[width="40%"]
--

. Sim. Por exemplo, o grafo abaixo.
+
--
image::images/cap4/img25.eps[width="40%"]
--

. {zwsp}
+
--
image::images/cap4/img27.eps[width="40%"]
--

. D
. B
. A
. C
. B
. C
. D (corresponde a latexmath:[$AEDCBA: 12+8+10+20+16=66$]) (Note que
esta é somente uma resposta aproximada, e o mínimo exato é
latexmath:[$ABDCEA = 16+12+10+15+12= 65$])
. A (latexmath:[$60/6 = 10$] únicas)
. C (corresponde a latexmath:[$ACEBDA$])
. B (que corresponde a latexmath:[$8+20+15 = 43$] minutos)
. Quando um componente tem latexmath:[$50-y$] vértices, terá
latexmath:[$(50-y)(49-y)/2$] arestas, e o outro tem
latexmath:[$50+y$] vértices
 e terá latexmath:[$(50+y)(49+y)/2$] arestas, totalizando
latexmath:[$2450+y^2$] arestas; quando cada componente tem igual
número de
 vértices, 50, cada um terá latexmath:[$50(50-1)/2 = 50 \cdot
49/2$] arestas, e latexmath:[$G$] terá o dobro disso, *2450*, que
será o mínimo desejado.

=== Recapitulando

Parabéns! Você concluiu o capítulo 6, só falta mais um capítulo!
E, se você foi disciplinado e realmente ``suou'' estudando 4 a 8 h
cada semana, deve ter aprendido muitas coisas da parte básica da
``Teoria dos Grafos'' que lhe serão indispensáveis ou muito úteis
em todo o resto do curso e sua vida profissional: conceitos básicos
e propriedades de grafos; grafos completos (cliques), bi e
k-partidos, regulares, rotulados, valorados, conexos, isométricos;
conceitos básicos de digrafos; representações de grafos e digrafos
em computadores; passeios, ciclos, trilhas, caminhos, circuitos,
grafos eulerianos e hamiltonianos, problemas do caminho mais curto,
do carteiro chinês e do caixeiro viajante. Muitas e importantes
novidades. Para você treinar ainda melhor, recomendamos a Lista de
Exercícios sobre Grafos, Prof. Antonio Alfredo Ferreira Loureiro,
http://goo.gl/ByNhuq, com soluções em http://goo.gl/jnmMSF.

No próximo capítulo, você será introduzido à Análise
Combinatória, que analisa estruturas e relações discretas
procurando determinar métodos de enumeração ou contagem nelas:
Você relembrará técnicas básicas de contagem (permutações,
arranjos, combinações), relações de recorrência e coeficientes
binomiais, e verá outras sequências de contagem e o teorema de
Ramsey.



////
Sempre termine os arquivos com uma linha em branco.
////
