8
Conceitos Basicos
Exerccio 8. Considere o caso geral do exerccio 1: Um qumico deseja embarcar os produtos
p1 , p2 , . . . , pn usando o menor n
umero de caixas. Alguns produtos n~ao podem ser colocados numa
mesma caixa porque reagem. Seja G o grafo que modela esse problema, onde vertices s~ao produtos
e arestas os pares que reagem, e denote por χ(G) o numero de mnimo de caixas de modo que seja
possvel encaixotar os produtos com seguranca. Prove que
1
χ(G) ≤ +
2
r
2m +
1
4
onde m e o numero de pares de produtos que reagem. (Dica: Em uma distribuic~ao mnima de
caixas, a cada duas caixas, precisa existir pelo menos um produto em uma caixa reagindo com um
produto da outra caixa. Assim podemos garantir um numero mnimo de arestas para o grafo, m.)
Exerccio 9. Chico e sua esposa foram a uma festa com tr^es outros casais. No encontro deles
houveram varios apertos de m~ao. Ninguem apertou a propria m~ao ou a m~ao da(o) esposa(o), e
ninguem apertou a m~ao da mesma pessoa mais que uma vez.
Apos os cumprimentos Chico perguntou para todos, inclusive para a esposa, quantas m~aos cada
um apertou e recebeu de cada pessoa uma resposta diferente. Quantas m~aos Chico apertou?
Exerccio 10. Prove que δ(G) ≤ d(G) ≤ ∆(G) para todo grafo G.
Exerccio 11. Decida se pode existir um grafo G com vertices que t^em graus 2, 3, 3, 4, 4, 5, respectivamente. E graus 2, 3, 4, 4, 5? Se sim, descreva-os.
Exerccio 12. Seja G um grafo com 14 vertices e 25 arestas. Se todo vertice de G tem grau 3 ou 5,
quantos vertices de grau 3 o grafo G possui?
Exerccio 13. Prove que em todo grafo de ordem pelo menos dois existem pelo menos dois vertices
com o mesmo grau. (Dica: comece por um caso pequeno, por exemplo ordem 3, antes de tentar
resolver o caso geral.)
Exerccio 14. Para um numero natural r, um grafo e r-regular se todos os vertices t^em grau r.
Para um grafo r-regular com n vertices e m arestas, expresse m em func~ao de n e r.
Exerccio 15. D^e exemplo de um grafo 3-regular que n~ao e completo.
Exerccio 16. Dado G, o grafo linha de G, denotado por LG, e o grafo cujos vertices s~ao as
arestas de G e um par de vertices dene uma aresta em LG se, e somente se, esses vertices s~ao
arestas adjacentes em G. Dado G determine |V(LG)| e |E(LG)|.
Exerccio 17. Prove que num grafo G com δ(G) > 0 e |E(G)| < |V(G)| existem pelo menos dois
vertices de grau 1.
1.2
Subgrafos
Dizemos que o grafo H e um subgrafo do grafo G se, e somente se, V(H) ⊆ V(G) e E(H) ⊆ E(G) e
nesse caso escrevemos H ⊆ G para indicar que H e subgrafo de G.
Exemplo 3. Considerando o grafo G do exemplo 1 temos que
G′
=
′′
=
G
s~ao subgrafos de G, enquanto que
H
=
I
=
J
=
1, 2, 5 , {1, 5}, {5, 2}, {1, 2}
3, 5, 6 , ∅
e
1, 2, 3 , {1, 2}, {3, 4} ,
1, 2, 3, 4, 9 , {1, 2}, {3, 4}
e
1, 2, 3, 4, 8 , {1, 2}, {3, 4}, {1, 8}
n~ao s~ao subgrafos de G pois: H n~ao e grafo, em I n~ao vale V(I) ⊆ V(G) e em J n~ao vale E(J) ⊆ E(G).
Subgrafos
9
Dados um grafo G e um subconjunto de vertices U ⊆ V(G), escrevemos G[U] para o subgrafo
induzido por U que e o subgrafo
U
G[U] = U, E(G) ∩
.
2
Analogamente, denimos subgrafo induzido por um subconjunto de arestas. Se M = {e1 , e2 , . . . , em } ⊆
E(G), ent~ao o subgrafo induzido por M, denotado , tem como conjunto de vertices e1 ∪e2 ∪· · ·∪em
e como conjunto de arestas o proprio M
G[M] =
m
[
i=1
ei , M .
Exemplo 4. Dos grafos G, H e I cujos diagramas s~ao dados na gura 1.2, podemos dizer que H e
um subgrafo induzido de G enquanto que I e um subgrafo mas n~ao e induzido.
a
b
a
b
a
c
d
c
e
G
b
d
e
d
H
e
I
Figura 1.2: Diagrama dos grafos G, H e I.
Um subgrafo H ⊆ G onde V(H) = V(G) e chamado de subgrafo gerador. No exemplo acima
I e subgrafo gerador de G, enquanto que H n~ao e subgrafo gerador de G.
1.2.1
Clique e conjunto independente
Se o subconjunto U ⊆ V(G) induz um subgrafo completo em G ent~ao chamamos U de clique em
G. Mais especicamente, se G[U] e um grafo completo com k vertices ent~ao dizemos que U e um
k-clique em G.
O caso particular de um 3-clique num grafo G e chamado de tri^angulo de G.
Por outro lado, se U ⊆ V(G) e tal que G[U] = (U, ∅) e chamado de conjunto independente
de G, ou k-conjunto-independente no caso |U| = k.
Exemplo 5. O subgrafo G ′ do exemplo 3 e um 3-clique e G ′′ do exemplo 3 e um 3-conjunto-
independente.
No grafo G do exemplo 1 os conjuntos {3, 5, 6} e {1, 4, 6, 8} s~ao independentes; no caso de {1, 4, 6, 8}
temos um conjunto independente de cardinalidade maxima pois n~ao ha naquele grafo conjunto
independente com 5 ou mais vertices. Nesse mesmo grafo, {8}, {6, 7} e {1, 2, 5} s~ao cliques, o ultimo
de cardinalidade maxima.
Observac~ao 2. O tamanho do maior clique e o tamanho do maior conjunto independente num grafo
G s~ao difceis de serem calculados computacionalmente. Eles pertencem a classe dos problemas NP-
difceis (veja [5], pagina 53). Uma consequ^encia desse fato e que n~ao e sabido se existem algoritmos
cujo tempo de execuc~ao no pior caso e um polin^omio em |V(G)|+|E(G)| para resolver esse problemas.
A descoberta de um algoritmo com tempo de pior caso polinomial no tamanho de G, ou a prova de
que ele n~ao existe, e um dos problemas n~ao-resolvidos mais importantes da atualidade, o problema
P × NP. Trata-se de um dos sete problemas do mil^enio [6], dos quais restam seis n~ao resolvidos,
cada um com uma recompensa de US$1.000.000,00 para uma soluc~ao, paga pelo Clay Mathematics
Institute.
10
Conceitos Basicos
1.2.2
Grafo bipartido e corte
Chamamos um grafo G de grafo bipartido se existem dois conjuntos independentes A e B em G
que particionam V(G), isto e, A e B s~ao tais que A ∩ B = ∅ e A ∪ B = V(G). Por exemplo, o
seguinte grafo e bipartido
V(G) = {1, 2, 3, 4, 5, 6, 7, 8}
E(G) = {{1, 6}, {6, 2}, {3, 7}, {3, 8}, {7, 4}, {7, 5}},
pois V(G) = {1, 2, 3, 4, 5} ∪ {6, 7, 8} e tanto {1, 2, 3, 4, 5} quanto {6, 7, 8} s~ao conjuntos independentes.
Notemos que a bipartic~ao pode n~ao ser unica, no caso do exemplo acima podemos escrever
V(G) = {6, 3, 4, 5} ∪ {1, 2, 7, 8} e tanto {6, 3, 4, 5} quanto {1, 2, 7, 8} s~ao conjuntos independentes. Para
evitar ambiguidades escrevemos um grafo bipartido G com bipartic~ao {A, B} como G = (A ∪ B, E).
Sejam G um grafo, A e B ⊂ V(G) dois subconjuntos disjuntos em V(G). Denimos o subconjunto
de arestas
E(A, B) = {u, v} ∈ E(G) : u ∈ A e v ∈ B ;
(1.11)
e o subgrafo bipartido induzido por A e B e o grafo bipartido
A ∪ B, E(A, B) .
Exemplo 6. A gura abaixo mostra as arestas de E(A, B) para A = {0, 1, 8} e B = {3, 4, 5, 6}.
0
8
1
7
2
6
3
5
4
Figura 1.3: E {0, 1, 8}, {3, 4, 5, 6} e formado pelas arestas {0, 4}, {0, 5}, {1, 3}, {1, 6}, {8, 3}, {6, 8} .
O conjunto de arestas E(A, A) e chamado de corte definido por A.
Exemplo 7. A gura abaixo mostra as arestas de E(A, B) para A = {0, 1, 8} e B = {3, 4, 5, 6}.
0
8
1
7
2
6
3
5
4
Figura 1.4:
O corte denido pelo conjunto {0, 1, 2, 7, 8}
{0, 4}, {0, 5}, {1, 3}, {1, 6}, {8, 3}, {6, 8}, {5, 7}, {6, 7}, {2, 3}, {2, 4} .
e formado pelas arestas
Da denic~ao de corte podemos escrever
E(G) = E(G[A]) ∪ E(G[A]) ∪ E(A, A).
Observac~ao 3. Convencionamos que os grafos triviais e vazio s~ao grafos bipartidos.
(1.12)
Subgrafos
1.2.3
11
Teorema de Mantel
Suponha que G = (V, E) e um grafo que n~ao contenha tri^angulo. Vamos determinar o numero
maximo de arestas que pode haver em G.
Seja A um conjunto independente em G de cardinalidade maxima. Como G n~ao contem
tri^angulos a vizinhanca de qualquer vertice e um conjunto independente, portanto temos
d(v) ≤ |A|,
para todo v ∈ V.
(1.13)
Como A e um conjunto independente em G podemos classicar as arestas de E(G) em dois tipos:
E1 s~ao as arestas de G que t^em exatamente um dos extremos fora de A e E2 s~ao as arestas de G
que tem ambos extremos fora de A. Dessa forma, o numero de arestas em E e |E1 | + |E2 | e
X
d(u) = |E1 | + 2|E2 | ≥ |E|.
u∈A
Usando (1.13) chegamos a
X
d(u) ≤
u∈A
X
|A| = |A||A|,
u∈A
portanto |E| ≤ |A||A|. Usando a desigualdade entre as medias aritmetica e geometrica1
|A||A| = |A|(|V| − |A|) ≤
|V|2
.
4
(1.14)
Assim, provamos o seguinte resultado que foi mostrado pela primeira vez por Mantel em 1906.
Teorema (Mantel, 1906).
Se G e um grafo sem tri^angulos ent~ao |E(G)| ≤ |V(G)|2 /4.
Esse teorema e um caso particular do famoso Teorema de Turan, que foi o princpio de um ramo
da teoria dos grafos chamada de Teoria Extremal de Grafos (veja mais sobre esse assunto em [1]).
Exercı́cios
Exerccio 18. Quantos subgrafos tem o grafo {1, 2, 3, 4, 5, 6}, {{1, 2}} ?
Exerccio 19. Quantos subgrafos completos tem o grafo completo de ordem n?
S
Exerccio 20. Sejam G um grafo e M ⊆ E(G). Tome o subconjunto U = e∈M e de vertices de G.
Prove ou d^e um contra-exemplo para G[U] = G[M].
Exerccio 21. Descubra um subgrafo induzido de
V(G) = {1, 2, 3, 4, 5, 6, 7, 8} e
E(G) = {{1, 2}, {1, 3}, {2, 3}, {2, 5}, {3, 6}, {8, 5}, {8, 6}, {5, 6}, {3, 4}, {5, 7}}
1-regular e com o maior n
umero possvel de arestas. (Qual a relac~ao com a resoluc~ao do exerccio
2?)
Exerccio 22. Mostre que em qualquer grafo G com pelo menos 6 vertices vale: ou G tem um
3-clique e G tem um 3-conjunto-independente, ou G tem um 3-conjunto-independente e G tem um
3-clique. (Dica: exerccio 7 e princpio da casa dos pombos sobre EK6 (v), para algum vertice v.)
Exerccio 23. Dado um grafo G, denotamos por α(G) a cardinalidade do maior conjunto independente em G,
α(G) = max |A| : A ⊂ V(G) e um conjunto independente .
Prove que se d(G) > α(G) ent~ao G contem tri^angulo, para todo G.
1
+···+a n
1 Desigualdade: (a a · · · a ) n
≤ a 1 +a 2n
.
n
1 2
(a − b)2 ≥ 0.
O caso
n=2
e simples e pode ser derivado do fato de que
12
Conceitos Basicos
Exerccio 24. Para todo grafo G, denotamos por ω(G) a cardinalidade do maior clique em G
ω(G) = max |A| : A ⊂ V(G) e um clique .
Prove que ω(G) = α(G).
Exerccio 25. Demonstre que as desigualdades abaixo valem para todo grafo G
(i) α(G) ≥ |V(G)|/(∆(G) + 1);
(ii) α(G) ≤ |E(G)|/δ(G), se δ(G) 6= 0;
(iii) ω(G) ≤ ∆(G) + 1.
Exerccio 26. Suponha H ⊆ G. Prove ou refute as desigualdades:
(i) α(H) ≤ α(G);
(iii) ω(G) ≤ ω(H);
(ii) α(G) ≤ α(H);
(iv) ω(H) ≤ ω(G).
Exerccio 27. Seja G um grafo bipartido. Prove que todo subgrafo de G e bipartido.
Exerccio 28. Seja G = (A ∪ B, E) um grafo bipartido qualquer e suponha que |A| < |B|. E verdade
que α(G) = |B|? Determine ω(G).
Exerccio 29. Um grafo bipartido G com partes A e B e dito completo se
E(G) = {{a, b} ⊆ V(G) : a ∈ A e b ∈ B}.
Um grafo bipartido completo sobre {A, B} com partes de cardinalidade |A| = n e |B| = m e denotado
por Kn,m (A, B). Determine |E(Kn,m (A, B))|.
Exerccio 30. Prove que todo grafo G tem um subgrafo bipartido H com |E(H)| ≥ |E(G)|/2.
Exerccio 31. Prove que todo grafo G tem um subgrafo gerador bipartido H tal que dH (v) ≥
dG (v)/2 para todo v ∈ V(G).
Exerccio 32. Prove a armac~ao da equac~ao (1.12).
Exerccio 33. Dado um grafo G, dena para todo U ⊆ V(G) a vizinhança de U, denotada NG (U),
por
[
NG (u).
NG (U) =
u∈U
verdade que |E(U, U)| = |NG (U)|? Justique.
E
Exerccio 34. Um grafo G e dito k-partido, para k ∈ N, se existem k conjuntos independentes A1 ,
A2 , . . . , Ak que particionam V(G), ou seja, V(G) = A1 ∪ A2 ∪ · · · ∪ Ak , o conjunto Ai e um conjunto
independente em G para todo i ∈ {1, 2, . . . , k} e Ai ∩ Aj = ∅ para quaisquer i e j distintos. Prove
que dentre os grafos k-partidos (k ≥ 2) completos com n vertices o numero maximo de arestas e
atingido quando |Ai | − |Aj | ≤ 1 para todos i, j ∈ {1, 2, . . . , n} distintos. D^e uma descric~ao desse grafo
k-partido de ordem n e com o maior n
umero possvel de arestas.
Exerccio 35. Mostre que, se n = kq + r com 0 ≤ r < k, ent~ao o numero de arestas do grafo do
exerccio anterior e
1
2
e que esse numero e limitado por
k−1
k
(n2 − r2 ) +
r
2
k−1 n
.
≤
k
2
Exerccio 36. Redena para todo grafo G o par^ametro χ(G) dado no exerccio 8 em func~ao dos
conjuntos independentes de G. Esse par^ametro de um grafo e conhecido na literatura como numero
cromatico2 do grafo (veja [4], captulo 5).
2 Computar
o n
umero crom
atico e um problema NP-dif
cil [5].
Isomorsmo
13
Exerccio 37. Prove que G e bipartido se e somente se χ(G) < 3.
Exerccio 38. Prove que as duas desigualdades dadas a seguir valem para todo grafo G com pelo
menos um vertice
|V(G)|
.
α(G)
ω(G) ≤ χ(G) e χ(G) ≥
(1.15)
Exerccio 39. Prove que todo grafo G satisfaz
χ(G) ≤ 1 + max δ(H).
H⊆G
1.3
Isomorfismo
Dizemos que os grafos G e H s~ao isomorfos e, nesse caso escrevemos G ≃ H, se existe uma func~ao
bijetora
f : V(G) → V(H)
(1.16)
tal que
(1.17)
{u, v} ∈ E(G) ⇐⇒ {f(u), f(v)} ∈ E(H)
para todos u, v ∈ V(G). Uma func~ao f como acima e chamada de isomorfismo.
Exemplo 8 (Grafo de Petersen). Os grafos representados na gura 1.5 s~ao isomorfos pelo isomorsmo f(1) = a, f(2) = b, f(3) = c, f(4) = d, f(5) = e, f(6) = f, f(7) = g, f(8) = h, f(9) = i,
f(10) = j. Esse grafo e chamado de grafo de Petersen, e um dos grafos mais conhecidos na Teoria
dos Grafos.
1
10
a
7
2
9
3
b
g
8
e
4
6
5
j
c
h
i
d
f
Figura 1.5: Grafos isomorfos (grafo de Petersen).
Notamos que quaisquer dois grafos completos G e H de mesma ordem s~ao isomorfos. Mais que
isso, qualquer bijec~ao entre V(G) e V(H) dene um isomorsmo entre eles. Nesse caso, dizemos que
o grafo e u
nico a menos de isomorsmos e por isso usamos a mesma notac~ao para todos eles, a
saber Kn , quando o conjunto dos vertices n~ao e relevante.
Exemplo 9. Ha oito grafos distintos com tr^es vertices, eles est~ao descritos nas representaco~es da
gura 1.6 abaixo.
3
2
3
1
3
2
3
1
2
3
1
1
1
1
2
3
1
1
2
3
2
2
Figura 1.6: Grafos distintos de ordem 3.
3
2
14
Conceitos Basicos
Figura 1.7: Grafos n~ao-isomorfos de ordem 3.
No entanto, ha apenas 4 grafos n~ao-isomorfos com tr^es vertices, representados pelos diagramas
da gura 1.7
N~ao existe uma caracterizac~ao simples de grafos isomorfos. Isso signica que n~ao ha algoritmo
eciente que recebe dois grafos e decide se eles s~ao isomorfos.
Exemplo 10. Nenhum dos grafos G, H e K representados na gura 1.8 s~ao isomorfos.
1
2
1
4
1
3
5
2
5
2
5
4
6
3
6
3
6
G
H
4
K
Figura 1.8: Grafos n~ao-isomorfos.
Temos que G n~ao e isomorfo a H porque G n~ao tem um vertice de grau quatro enquanto que
o vertice 5 em H tem grau quatro, portanto n~ao ha como haver uma bijec~ao entre os vertices
desse grafo que preserve as adjac^encias. Pelo mesmo motivo H n~ao e isomorfo a K. Agora, G n~ao
e isomorfo a K porque caso existisse um isomorsmo f : V(G) → V(K) ent~ao a imagem por f do
conjunto {2, 3, 5} ⊂ V(G) e, obrigatoriamente, o conjunto {2, 3, 5} ⊂ V(K), mas qualquer bijec~ao f
n~ao preserva adjac^encia entre esses vertices pois {2, 3, 5} em G induz um tri^angulo e em K n~ao (veja
o exerccio 42 abaixo).
Nesse exemplo foram dados argumentos diferentes para concluir o mesmo fato, o n~ao-isomorsmo
entre pares de grafos. Ainda, existem exemplos de grafos n~ao isomorfos para os quais esses argumentos n~ao funcionam (da mesma forma que a exist^encia de um vertice de grau quatro funciona
para mostrar que G n~ao e isomorfo a H mas n~ao serve para mostrar que G n~ao e isomorfo a K pois
1, 2, 2, 3, 3, 3 s~ao os graus dos vertices de ambos os grafos).
Observac~ao 4. E difcil caracterizar de modo eciente o n~ao-isomorsmo entre grafos:
O problema do n~
ao-isomorsmo de grafos : Dados os grafos G = (V, E) e H = (V, E ′ ) decidir
se eles s~ao n~ao-isomorfos.
N~ao se conhece algoritmo de tempo polinomial no tamanho dos grafos para decidir se dois grafos
n~ao s~ao isomorfos. Mais do que isso, n~ao se conhece um algoritmo de tempo polinomial que receba
como entrada uma terna (G, H, P) onde P e uma prova de que G e H n~ao s~ao isomorfos e que devolva
sim se G1 n~ao e isomorfo a G2 e devolva n~ao caso contrario. Em linguagem tecnica dissemos que
n~ao se sabe se o problema do n~ao-isomorsmo de grafos esta na classe NP de complexidade
computacional.
Observac~ao 5. Por outro lado, podemos considerar o problema do isomorsmo de grafos:
O problema do isomorsmo de grafos : Dados os grafos G = (V, E) e H = (V, E ′ ) decidir se
eles s~ao isomorfos.
Outras noc~oes de grafos
15
Atualmente n~ao se conhece algoritmo polinomial no tamanho do grafo que resolva o problema.
Entretanto, n~ao e difcil projetar um algoritmo de tempo polinomial que recebe a terna (G, H, f)
onde f : V(G) → V(H) e devolve sim caso G e H s~ao isomorfos e f e o isomorsmo, caso contrario
devolve n~ao. Em linguagem tecnica dizemos que o problema do isomorsmo de grafos esta na
classe NP de complexidade de problemas computacionais. Entretanto, n~ao e sabido se esse
problema e NP-completo.
Exercı́cios
Exerccio 40. Determine quais pares dentre os grafos abaixo s~ao isomorfos.
(i) G1 dado por V(G1 ) = {v1 , u1 , w1 , x1 , y1 , z1 } e
E(G1 ) = {{u1 , v1 }, {u1 , w1 }, {v1 , w1 }, {v1 , x1 }, {w1 , y1 }, {x1 , y1 }, {x1 , z1 }};
(ii) G2 dado por V(G2 ) = {v2 , u2 , w2 , x2 , y2 , z2 } e
E(G2 ) = {{u2 , v2 }, {u2 , w2 }, {v2 , w2 }, {v2 , x2 }, {w2 , y2 }, {x2 , y2 }, {y2 , z2 }};
(iii) G3 dado por V(G3 ) = {v3 , u3 , w3 , x3 , y3 , z3 } e
E(G3 ) = {{u3 , v3 }, {u3 , w3 }, {v3 , w3 }, {v3 , x3 }, {w3 , y3 }, {x3 , y3 }, {u3 , z3 }}.
Exerccio 41. Mostre que existem 11 grafos n~ao-isomorfos com 4 vertices.
Exerccio 42. Sejam G e H grafos isomorfos e f : V(G) → V(H) um isomorsmo. E verdade que
G[U] e isomorfo a H[f(U)] para todo U ⊆ V(G)? Justique.
Exerccio 43. Mostre que o grafo de Petersen e isomorfo ao complemento do grafo linha do K5 .
Exerccio 44. Um automorfismo de um grafo e um isomorsmo do grafo sobre ele mesmo. Quantos
automorsmos tem um grafo completo?
Exerccio 45. Mostre que o conjunto de automorsmos de um grafo com a operac~ao de composic~ao
de funco~es denem um grupo.
Exerccio 46. Qual o numero de grafos distintos sobre um conjunto de vertices V de tamanho n?
Exerccio 47. Prove que ha pelo menos
de ordem n.
2( 2 )
n!
n
grafos n~ao isomorfos sobre um conjunto de vertices
Exerccio 48. Um grafo G = (V, E) e vértice-transitivo se para quaisquer u, v ∈ V existe um
automorsmo f de G com f(v) = u. Analogamente, G e aresta-transitivo se para quaisquer
arestas {x, y}, {z, w} ∈ E existe um automorsmo f de G tal que {f(x), f(y)} = {z, w}.
D^e um exemplo de grafo vertice-transitivo. D^e um exemplo de grafo aresta-transitivo. D^e um
exemplo de grafo aresta-transitivo mas n~ao vertice-transitivo.
1.4
Outras noções de grafos
Em algumas situac~oes podemos ter um modelo para um problema a ser resolvido e esse modelo
seria um grafo se desconsiderassemos algumas peculiaridades da situac~ao. Por exemplo, um mapa
rodoviario pode ser modelado denindo-se um vertice para cada cidade e duas cidades formam
uma aresta no grafo (modelo) se existe rodovia ligando essas cidades correspondentes aos vertices.
Normalmente, dist^ancia e um par^ametro importante nesses mapas e assim as arestas devem ter um
comprimento associado a elas. Entretanto, \comprimento de aresta" n~ao faz parte da denic~ao de
um grafo. Num outro exemplo, se estamos interessados em rotas de trafego dentro de uma cidade
podemos denir um vertice por esquina e duas esquinas consecutivas numa mesma rua formam uma
aresta. Nesse caso, as ruas t^em sentido (m~ao e contra-m~ao) e as arestas tambem deveriam ter mas,
novamente, essa caracterstica n~ao faz parte da denic~ao de grafos.
Esses problemas e muitos outros podem ser modelados com \outros tipos" de grafos. Alguns
desses outros tipos s~ao