Teoria Dos Grafos

Prévia do material em texto

Universidade Estadual De Santa Cruz - UESC.
Prof ª Larissa Brito de Oliveira
Disciplina: Análise Combinatória
Aluna: Natália Alencar.
Teoria de Grafos
1 Tipos Especiais de Grafos
1.1 Grafo Completo
Um grafo completo é definido como um grafo onde todo par de vértices é ligado por uma aresta.
Um grafo completo com n vértices é denotado por Kn.
Figura 1: O grafo completo de k6
1.2 Grafo Complementar
O grafo complementar do grafo G, é denotado por G. Temos que V(G)=V(G) e que A(G) ∪
A(G) inclui todas as arestas de G.
Figura 2: Dois grafos complementares
1
1.3 Grafo nulo ou vazio
Um grafo G é nulo ou vazio quando o conjunto de arestas A(G) é vazio.
Figura 3: Grafo nulo ou vazio
1.4 Grafo Regular
Um grafo é regular (de grau k ou ainda k-regular) quando todos os seus vértices têm o mesmo
grau (k).
Exemplo - A figura 4 mostra um grafo 3-regular, isto é, todos os vértices tem grau 3.
Figura 4: Um grafo k-regular de grau 3
1.5 Ciclo
Um ciclo é um grafo conexo regular de grau 2. A notação é Cn
Figura 5: Exemplos de ciclo: C5 e C6
2
1.6 Caminho
Um caminho é um ciclo do qual retiramos uma aresta. O comprimento do caminho é dado pelo
número de arestas. Assim, o caminho Pn é obtido retirando uma aresta do ciclo Cn + 1
Figura 6: Exemplos de ciclo: P4 e C5
1.7 Árvores
Uma árvore é um grafo conexo sem ciclos como subgrafos.
Figura 7: Exemplos de Árvores
1.7.1 Folha
É todo vértice de grau 1 de uma árvore.
Figura 8: Exemplos de Folhas
3
1.7.2 Floresta
Um grafo cujas componentes conexas são árvores.
Figura 9: Exemplo de Floresta
1.8 Grafos Bipartidos
É um grafo em que o conjunto V de vértices pode ser particionado em dois subconjuntos disjuntos
V1 e V2 tal que toda aresta de G tem uma extremidade em V1 e outra em V2. O subconjunto V1 é
dito um subconjunto independente de vértices do grafo G pois não há arestas ligando dois vértices
de V1. Temos também que V2 é um subconjunto independente de vértices de G.
Figura 10: Exemplo de Bipartido
1.8.1 Grafos Bipartidos Completos
É um grafo bipartido em que todos os vértices de V1 são ligados a todos os vértices de V2.
Denotado por Kp,q.
Figura 11: Exemplo de Bipartido Completo K2,4
4
2 Árvores
Um dos tipos mais frequentes de grafos são as árvores, já definidos anteriormente como grafos
conexos sem ciclos. Um grafo cujas componentes conexas são árvores é chamado de floresta. E todo
vértice de grau 1 da árvore é uma folha.
Teorema 1. Toda árvore, com ao menos uma aresta, possui uma folha.
Demonstração: Escolhemos um vértice da árvore.
• Se o vértice tem grau 1, a proposição é válida.
• Se o vértice tem grau maior que 1, podemos seguir uma das arestas para outro vértice.
O caminho é único
Suponhamos que existam 2 caminhos distintos P e Q ligando dois vértices x,y ∈ VG.
Logo, existe uma aresta δ = (u,v) ∈ AG tal que δ ∈ P e δ /∈ Q ( sem perda de generalidade ) .
PQ é um subgrafo conexo de G, logo, em PQ - δ existe um passeio de u a v.
Então, pelo item anterior, existe um caminho R de u a v em PQ - δ . Portanto, R ∪ δ é um
ciclo em G. Absurdo, visto que G é árvore.
Teorema 2. Se G é uma árvore com n vértices, então G possui n-1 arestas.
Demonstração: Vamos mostrar usando indução matemática sobre n. Vamos verificar o resultado
para um valor particular de n. Por exemplo,
Base: n = 1 e n = 2.
Para n = 1, temos 0 arestas.
Para n = 2 temos 1 aresta.
Hipótese de Indução
Se G é uma árvore com k < n vértices, então G possui k-1 arestas.
Passo: n > 1.
Vamos supor agora que o resultado vale para um grafo G’ com k − 1 vértices. Isto é, se G’ é
uma árvore então G’ é conexo e possui k − 2 arestas. Vamos acrescentar uma nova aresta (v,w) a
este grafo. Para manter o grafo conexo e sem circuitos um e apenas um dos vértices em (v,w) pode
pertencer a G’. Assim ao acrescentar a aresta(v,w) a G’, precisamos acrescentar também um vértice.
Assim teremos um novo grafo G”com k vértices e k − 1 arestas. A forma como G”foi constrúıdo
garante que é conexo e sem circuitos. Portanto temos que G”é uma árvore.
Mostramos assim que se G é uma árvore então G é conexo com n− 1 arestas.
Exemplo - (Rede de Vôlei):Uma certa rede de vôlei possui 20x50 quadradinhos. Com o passar
do tempo, alguns dos barbantes que conectam os vértices dos quadradinhos podem se romper, entre-
tanto, será necessário que vários barbantes arrebentem para que a rede se desfaça em dois ou mais
pedaços. Qual é o número máximo de barbantes que podemos cortar de modo que a rede continue
em um pedaço após os cortes?
5
Resposta: Contando inicialmente o total de arestas e vértices que contem na rede, temos
Total de Arestas: 20 x 51 + 21 x 50
Total de nós (vértices): 51 x 21
então, no grafo obtido após todos os cortes haverá 51 x 21 -1 arestas. Portanto, o número máximo
de barbantes que podemos cortar será de
= 20x51 + 21x51− (51x21− 1)
= 20x51 + 21x51− (20x51 + 51− 1)
= 21x50− 50
= 20x50
6