Caderno de Macs
[Assunto5 – Modelos de grafos.]
5.1-Noções básicas-Grafos.
( Grafo, ordem do grafo, grafo conexo, completo, orientado... )
Grafo- é um esquema constituído por pontos (ou vértices) e por segmentos (ou
arestas) que unem esses pontos.
Exemplo: observemos o grafo:
Este grafo tem os vértices A, B, C, D.
As arestas são os segmentos de reta que unem os vértices. Neste caso:
[AB], [AD], [BC], [BD]
… por ter quatro vértices, dizemos que é um grafo de ordem 4.
Ordem de um grafo é o número de vértices desse grafo
Algumas definições.
Exemplo:
O vértice E é isolado, pois não tem qualquer aresta a incidir nele
Vértice diz-se isolado- não existem arestas a incidir nele.
O vértice F é terminal, pois tem apenas uma aresta a incidir.
Vértices terminais- têm apenas uma aresta incidente.
Os vértices A e B são adjacentes, pois têm uma aresta a ligá-los.
Vértices adjacentes- Têm alguma aresta a ligá-los.
No vértice C, existe uma aresta que a ele próprio. Essa aresta designa-se lacete.
Lacete- Aresta que liga um vértice a ele próprio.
As arestas [AB] e [AD] dizem-se adjacentes, pois incidem num mesmo vértice, A.
Arestas adjacentes- Incidem num mesmo vértice.
Entre B e D, existem duas arestas distintas a ligá-las. As arestas [BD] [BD] dizem-se
paralelas.
Arestas paralelas- arestas distintas que ligam o mesmo par de vértices.
O grafo do exemplo anterior não apresentava arestas paralelas nem lacetes.
Nesse caso dizemos tratar-se de um grafo simples.
Grafo simples- é um grafo que não tem arestas paralelas nem lacetes.
O segundo grafo apresenta arestas paralelas e lacetes, por isso é classificado como
multigrafo.
Multigrafo- Grafo que não é simples.
Um grafo diz-se conexo se existir sempre uma sequência de arestas a unir
quaisquer dois dos seus vértices.
Exemplo este grafo:
é conexo ,pois existe sempre uma sequência de vértices a unir quaisquer dois dos seus
vértices.
Este grafo:
não é conexo. Por exemplo, não existe nenhuma aresta, nem qualquer sequência de
arestas a ligar os vértices A e C.
Exemplo.
No grafo seguinte,
indicámos o sentido D→A→B→ C→ E, colocando sentidos nas arestas. Dizemos que o
grafo é orientado.
Dígrafo, ou grafo Orientado, é um grafo em que as arestas têm orientações (ou
sentidos) definidas.
Exemplo podemos usar sentidos para desenhar esta figura, sem levantar o lápis:
Começamos na letra C, percorremos todas as arestas e terminamos no ponto F.
Sequência de letras: C→ B→A→F→E→D→C→F
Grafo completo é um grafo em que cada um dos vértices é adjacente a todos os
outros.
Exemplo:
Grafo completo de ordem 2: tem duas arestas
Grafo completo de ordem 3: tem três arestas
Grafo completo de ordem 4: tem 6 arestas.
Grafo completo de ordem 5: tem 10 arestas.
Questão: quantas arestas tem um grafo completo de ordem 6? E de ordem 7? E de
ordem 10? E de ordem n?
Sugestão: para o grafo completo de ordem n, o número de arestas é dado por:
𝑛×(𝑛−1)
. Descubra porquê.
2
Solução:
ordem 6 tem (65)/2 = 15 arestas;
ordem 7 tem (76)/2 = 21 arestas,
ordem 10 tem (109)/2 = 45 arestas.
Nota: Por exemplo, no grafo completo de ordem 5,
cada vértice liga a quatro arestas, o que dá 54= 20, no entanto, quando ligamos A a
B, com a aresta [AB], também estamos a ligar B a A. Deste modo, as arestas distintas
são apenas metade do cálculo anterior, isto é
5×4
= 10,
2
como facilmente se pode constatar nos exemplos vistos.
Exemplo: Apertos de mão
Suponha que 5 amigos, que representamos por A, B, C, D, E se encontram e todos
cumprimentam todos com um aperto de mão. Quantos serão ao todo os apertos de
mão?
Representando a situação pelo esquema:
Facilmente percebemos que este problema é semelhante à soma das arestas de um
grafo completo de ordem 5. De facto, cada amigo cumprimenta os outros quatro, mas,
quando “A” cumprimenta “B”, “B” já não precisa voltar a cumprimentar “A” Ao todo
são
5×4
= 10 apertos de mão
2
Nota:
Repare ainda que no grafo dado:
Todos os vértices têm grau 4. A soma de todos os graus será 54=20. O número de
arestas é 10. Exatamente metade.
Lema do aperto de mão:
“Em qualquer grafo, a soma dos graus de todos os seus vértices é igual ao dobro do
número de arestas”
Exemplo:
Soma dos graus de todos os vértices: 2+3+1+2= 8 arestas: 4
2 4=8 (lema do aperto de mão)
Exemplo
Consideremos o grafo:
A soma dos graus de todos os seus vértices é 2+2+3+3+2+2=14. Repare ainda que o
grafo tem exatamente 7 arestas, que é metade da soma dos graus.
Sugestão: experimente outros grafos. Verá que este lema é sempre válido.
Ponte- é uma aresta de um grafo que, se for retirada, torna o grafo desconexo.
Exemplo: neste grafo,
a aresta [BF] é uma ponte. Se for retirada, o grafo deixa de ser conexo.
Existem outras pontes, tais como [BC] e [EF].
Exemplo
O grafo seguinte:
Não tem qualquer ponte. Podemos retirar qualquer aresta (única), que o grafo
continua a ser conexo.
-é é ê