Algoritmos e Teoria dos GrafosAula 07

Prof. Murilo V. G. da Silva

DINF/UFPR

Material da Disciplina:

Renato J. S. Carmo

Graus de vertices em trilhas

Teorema

Se T e uma trilha sobre um grafo G , entao o grau de todo vertice interno de Tem G [T ] e par.

Prova: (em sala)

Corolario

Se T e uma trilha fechada sobre um grafo G , entao o grau de todo vertice emG [T ] e par.

Prova: Exercıcio

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Graus de vertices em trilhas

Teorema

Se T e uma trilha sobre um grafo G , entao o grau de todo vertice interno de Tem G [T ] e par.

Prova: (em sala)

Corolario

Se T e uma trilha fechada sobre um grafo G , entao o grau de todo vertice emG [T ] e par.

Prova: Exercıcio

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Graus de vertices em trilhas

Teorema

Se T e uma trilha sobre um grafo G , entao o grau de todo vertice interno de Tem G [T ] e par.

Prova: (em sala)

Corolario

Se T e uma trilha fechada sobre um grafo G , entao o grau de todo vertice emG [T ] e par.

Prova: Exercıcio

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Graus de vertices em trilhas

Teorema

Se T e uma trilha sobre um grafo G , entao o grau de todo vertice interno de Tem G [T ] e par.

Prova: (em sala)

Corolario

Se T e uma trilha fechada sobre um grafo G , entao o grau de todo vertice emG [T ] e par.

Prova: Exercıcio

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Caminhos

Teorema

Se P e um caminho maximal em um grafo G , entao todos os vizinhos de suas pontasestao em P.

Prova: (em sala)

Teorema

Se P e um caminho direcionado maximal em um grafo direcionado G , entao

todos os vizinhos de entrada de seu vertice inicial estao em P, e

todos os vizinhos de saıda seu vertice final estao em P.

Prova: (exercıcio)

Teorema

Todo passeio de tamanho mınimo entre dois vertices de um grafo e um caminho.

Prova: (em sala)

Exercıcio: Prove o mesmo resultado para grafos direcionados

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Caminhos

Teorema

Se P e um caminho maximal em um grafo G , entao todos os vizinhos de suas pontasestao em P.

Prova: (em sala)

Teorema

Se P e um caminho direcionado maximal em um grafo direcionado G , entao

todos os vizinhos de entrada de seu vertice inicial estao em P, e

todos os vizinhos de saıda seu vertice final estao em P.

Prova: (exercıcio)

Teorema

Todo passeio de tamanho mınimo entre dois vertices de um grafo e um caminho.

Prova: (em sala)

Exercıcio: Prove o mesmo resultado para grafos direcionados

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Caminhos

Teorema

Se P e um caminho maximal em um grafo G , entao todos os vizinhos de suas pontasestao em P.

Prova: (em sala)

Teorema

Se P e um caminho direcionado maximal em um grafo direcionado G , entao

todos os vizinhos de entrada de seu vertice inicial estao em P, e

todos os vizinhos de saıda seu vertice final estao em P.

Prova: (exercıcio)

Teorema

Todo passeio de tamanho mınimo entre dois vertices de um grafo e um caminho.

Prova: (em sala)

Exercıcio: Prove o mesmo resultado para grafos direcionados

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Caminhos

Teorema

Se P e um caminho maximal em um grafo G , entao todos os vizinhos de suas pontasestao em P.

Prova: (em sala)

Teorema

Se P e um caminho direcionado maximal em um grafo direcionado G , entao

todos os vizinhos de entrada de seu vertice inicial estao em P, e

todos os vizinhos de saıda seu vertice final estao em P.

Prova: (exercıcio)

Teorema

Todo passeio de tamanho mınimo entre dois vertices de um grafo e um caminho.

Prova: (em sala)

Exercıcio: Prove o mesmo resultado para grafos direcionados

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Caminhos

Teorema

Se P e um caminho maximal em um grafo G , entao todos os vizinhos de suas pontasestao em P.

Prova: (em sala)

Teorema

Se P e um caminho direcionado maximal em um grafo direcionado G , entao

todos os vizinhos de entrada de seu vertice inicial estao em P, e

todos os vizinhos de saıda seu vertice final estao em P.

Prova: (exercıcio)

Teorema

Todo passeio de tamanho mınimo entre dois vertices de um grafo e um caminho.

Prova: (em sala)

Exercıcio: Prove o mesmo resultado para grafos direcionados

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Caminhos

Teorema

Se P e um caminho maximal em um grafo G , entao todos os vizinhos de suas pontasestao em P.

Prova: (em sala)

Teorema

Se P e um caminho direcionado maximal em um grafo direcionado G , entao

todos os vizinhos de entrada de seu vertice inicial estao em P, e

todos os vizinhos de saıda seu vertice final estao em P.

Prova: (exercıcio)

Teorema

Todo passeio de tamanho mınimo entre dois vertices de um grafo e um caminho.

Prova: (em sala)

Exercıcio: Prove o mesmo resultado para grafos direcionados

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Caminhos

Teorema

Se P e um caminho maximal em um grafo G , entao todos os vizinhos de suas pontasestao em P.

Prova: (em sala)

Teorema

Se P e um caminho direcionado maximal em um grafo direcionado G , entao

todos os vizinhos de entrada de seu vertice inicial estao em P, e

todos os vizinhos de saıda seu vertice final estao em P.

Prova: (exercıcio)

Teorema

Todo passeio de tamanho mınimo entre dois vertices de um grafo e um caminho.

Prova: (em sala)

Exercıcio: Prove o mesmo resultado para grafos direcionados

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Caminhos mınimos

Definicao de caminho mınimo

Caminho mınimo: Um caminho de tamanho mınimo

O mesmo vale para grafos direcionados

No caso de grafos com pesos trata-se de um caminho de peso mınimo

Teorema

Todo segmento de caminho mınimo em um grafo G e caminho mınimo em G .

Exercıcio: Prove o teorema acima e tambem a versao direcionada do teorema

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Caminhos mınimos

Definicao de caminho mınimo

Caminho mınimo: Um caminho de tamanho mınimo

O mesmo vale para grafos direcionados

No caso de grafos com pesos trata-se de um caminho de peso mınimo

Teorema

Todo segmento de caminho mınimo em um grafo G e caminho mınimo em G .

Exercıcio: Prove o teorema acima e tambem a versao direcionada do teorema

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Caminhos mınimos

Definicao de caminho mınimo

Caminho mınimo: Um caminho de tamanho mınimo

O mesmo vale para grafos direcionados

No caso de grafos com pesos trata-se de um caminho de peso mınimo

Teorema

Todo segmento de caminho mınimo em um grafo G e caminho mınimo em G .

Exercıcio: Prove o teorema acima e tambem a versao direcionada do teorema

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Caminhos mınimos

Definicao de caminho mınimo

Caminho mınimo: Um caminho de tamanho mınimo

O mesmo vale para grafos direcionados

No caso de grafos com pesos trata-se de um caminho de peso mınimo

Teorema

Todo segmento de caminho mınimo em um grafo G e caminho mınimo em G .

Exercıcio: Prove o teorema acima e tambem a versao direcionada do teorema

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Caminhos mınimos

Definicao de caminho mınimo

Caminho mınimo: Um caminho de tamanho mınimo

O mesmo vale para grafos direcionados

No caso de grafos com pesos trata-se de um caminho de peso mınimo

Teorema

Todo segmento de caminho mınimo em um grafo G e caminho mınimo em G .

Exercıcio: Prove o teorema acima e tambem a versao direcionada do teorema

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Ciclos

Ciclo (ou circuito)

Um ciclo e uma trilha fechada cujos vertices sao todos distintos, exceto pelas pontas.

Cn: Um grafo induzido por um ciclo de n vertices

Grafo acıclico: Um grafo que nao contem nenhum ciclo

Uma corda do ciclo C em um grafo G e uma aresta ligando dois vertices naoadjacentes G [C ]

Cintura

A cintura de um grafo G e o tamanho um ciclo de tamanho mınimo em G e edenotada por γ(G).

Convencao: Se G e acıclico, γ(G) = ∞.

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Ciclos

Ciclo (ou circuito)

Um ciclo e uma trilha fechada cujos vertices sao todos distintos, exceto pelas pontas.

Cn: Um grafo induzido por um ciclo de n vertices

Grafo acıclico: Um grafo que nao contem nenhum ciclo

Uma corda do ciclo C em um grafo G e uma aresta ligando dois vertices naoadjacentes G [C ]

Cintura

A cintura de um grafo G e o tamanho um ciclo de tamanho mınimo em G e edenotada por γ(G).

Convencao: Se G e acıclico, γ(G) = ∞.

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Ciclos

Ciclo (ou circuito)

Um ciclo e uma trilha fechada cujos vertices sao todos distintos, exceto pelas pontas.

Cn: Um grafo induzido por um ciclo de n vertices

Grafo acıclico: Um grafo que nao contem nenhum ciclo

Uma corda do ciclo C em um grafo G e uma aresta ligando dois vertices naoadjacentes G [C ]

Cintura

A cintura de um grafo G e o tamanho um ciclo de tamanho mınimo em G e edenotada por γ(G).

Convencao: Se G e acıclico, γ(G) = ∞.

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Ciclos

Ciclo (ou circuito)

Um ciclo e uma trilha fechada cujos vertices sao todos distintos, exceto pelas pontas.

Cn: Um grafo induzido por um ciclo de n vertices

Grafo acıclico: Um grafo que nao contem nenhum ciclo

Uma corda do ciclo C em um grafo G e uma aresta ligando dois vertices naoadjacentes G [C ]

Cintura

A cintura de um grafo G e o tamanho um ciclo de tamanho mınimo em G e edenotada por γ(G).

Convencao: Se G e acıclico, γ(G) = ∞.

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Ciclos

Ciclo (ou circuito)

Um ciclo e uma trilha fechada cujos vertices sao todos distintos, exceto pelas pontas.

Cn: Um grafo induzido por um ciclo de n vertices

Grafo acıclico: Um grafo que nao contem nenhum ciclo

Uma corda do ciclo C em um grafo G e uma aresta ligando dois vertices naoadjacentes G [C ]

Cintura

A cintura de um grafo G e o tamanho um ciclo de tamanho mınimo em G e edenotada por γ(G).

Convencao: Se G e acıclico, γ(G) = ∞.

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Ciclos

Ciclo (ou circuito)

Um ciclo e uma trilha fechada cujos vertices sao todos distintos, exceto pelas pontas.

Cn: Um grafo induzido por um ciclo de n vertices

Grafo acıclico: Um grafo que nao contem nenhum ciclo

Uma corda do ciclo C em um grafo G e uma aresta ligando dois vertices naoadjacentes G [C ]

Cintura

A cintura de um grafo G e o tamanho um ciclo de tamanho mınimo em G e edenotada por γ(G).

Convencao: Se G e acıclico, γ(G) = ∞.

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Ciclos

Teorema

Um grafo tem ciclo ⇔ tem caminhos distintos com os mesmos inıcio e fim.

Prova: em sala

Corolario

Um grafo e bipartido se e somente se nao tem ciclo ımpar.

Prova: Exercıcio

Corolario

Todo grafo acıclico e bipartido.

Prova: Exercıcio

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Ciclos

Teorema

Um grafo tem ciclo ⇔ tem caminhos distintos com os mesmos inıcio e fim.

Prova: em sala

Corolario

Um grafo e bipartido se e somente se nao tem ciclo ımpar.

Prova: Exercıcio

Corolario

Todo grafo acıclico e bipartido.

Prova: Exercıcio

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Ciclos

Teorema

Um grafo tem ciclo ⇔ tem caminhos distintos com os mesmos inıcio e fim.

Prova: em sala

Corolario

Um grafo e bipartido se e somente se nao tem ciclo ımpar.

Prova: Exercıcio

Corolario

Todo grafo acıclico e bipartido.

Prova: Exercıcio

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Ciclos

Teorema

Um grafo tem ciclo ⇔ tem caminhos distintos com os mesmos inıcio e fim.

Prova: em sala

Corolario

Um grafo e bipartido se e somente se nao tem ciclo ımpar.

Prova: Exercıcio

Corolario

Todo grafo acıclico e bipartido.

Prova: Exercıcio

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Ciclos

Teorema

Um grafo tem ciclo ⇔ tem caminhos distintos com os mesmos inıcio e fim.

Prova: em sala

Corolario

Um grafo e bipartido se e somente se nao tem ciclo ımpar.

Prova: Exercıcio

Corolario

Todo grafo acıclico e bipartido.

Prova: Exercıcio

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos

Ciclos

Teorema

Um grafo tem ciclo ⇔ tem caminhos distintos com os mesmos inıcio e fim.

Prova: em sala

Corolario

Um grafo e bipartido se e somente se nao tem ciclo ımpar.

Prova: Exercıcio

Corolario

Todo grafo acıclico e bipartido.

Prova: Exercıcio

Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos