Slide grafos

Prévia do material em texto

Teoria dos grafos
5º PERÍODO – CURSO COMPLETO
APRESENTAÇÃO
Tenorio
www.osfedera.com
tenorio.petrolina@bol.com.br
APRESENTAÇÃO - EMENTA
GRAFOS
TIPOS E PROPRIEDADES DOS GRAFOS;
COMPLEXIDADE ALGORITMICA;
APRESENTAÇÃO - REFERÊNCIAS
BOAVENTURA NETTO, Paulo Oswaldo. Grafos. Teoria, Modelos, Algoritmos. Editora Edgard Blücher Ltda, São Paulo, 2003.
SZWARCFITER, Jayme Luiz. Grafos e Algoritmos Computacionais. Editora Campus Ltda, Rio de Janeiro, 1984.
TOSCANI, Laira Vieira e VELOSO, Paulo A. S. Complexidade de Algoritmos. 2ª Edição. Sagra Luzzatto, Porto Alegre, 2005.
 
APRESENTAÇÃO - AVALIAÇÃO
1ª NOTA: 
1 prova valendo 10,00 + 1 exercícios valendo 1,0 extra.
Assunto: Todo o conteúdo teórico
2ª NOTA: 
1 trabalho valendo 10,00
Assunto:  Programação em Grafos
3ª NOTA: 
1 prova valendo 10,00.	Assunto:  Todo o conteúdo teórico
FINAL: 
1 prova valendo 10,00.	Assunto:  Todo o conteúdo teórico
APRESENTAÇÃO – DÚVIDAS?
TEORIA DOS GRAFOS
CONCEITO
Um grafo G(V, E) é um conjunto V finito, não-vazio de vértices, conectados por um conjunto de arestas.
V = {v1, v2, v3, v4, v5} 
E = {a1, a2, a3, a4, a5, a6}
onde a1 = (v1, v2), 
a2 = (v1, v3), a3 = (v2, v3), 
a4 = (v2, v5), a5 = (v3, v5), 
a6 = (v3, v4);
DENSIDADE
DENSIDADE DE VÉRTICES: QUANTIDADE DE VÉRTICES, DENOTADO PELA LETRA N
DENSIDADE DE ARESTAS: QUANTIDADE DE ARESTAS, DENOTADO PELA LETRA M
N = 5
M = 6
GRAFO TRIVIAL
Um grafo é chamado de Trivial se tiver apenas um vértice e nenhuma aresta.
ADJACÊNCIA
Duas arestas são consideradas adjacentes se possuírem um vértice em comum. 
Dois vértices são adjacentes se possuírem uma aresta em comum.
LAÇO
Um laço é uma aresta que possui as duas extremidades em um mesmo vértice de G.
MULTIGRAFO
Um multigrafo é um grafo que possui, pelo menos, um par de arestas com vértices iguais.
a1 e a4
a5, a7 e a8
GRAU
O GRAU DE UM VÉRTICE É A QUANTIDADE DE TOQUES DE ARESTAS NESTE VÉRTICE.
REGULAR
REGULAR DE GRAU OU APENAS REGULAR É O GRAFO ONDE TODOS SO VÉRTICES TEM O MESMO GRAU.
Em um grafo regular:
M = (G * N) 
 2 
DELTA E CÚBICO
O grau um grafo, denominado de Delta é o grau do maior vértice do grafo. 
Um grafo regular de grau 3 é chamado de grafo Cúbico. 
ALTAMENTE IRREGULAR
Um grafo é chamado de altamente irregular se cada um dos vértices do grafo é adjacente, apenas, a vértices de graus diferentes do seu.
RÓTULO E VALORAÇÃO (PESOS)
ROTULO: NOMEAÇÃO ALEATÓRIA
VALORAÇÃO (PESOS): NOMEAÇÃO ASSOCIADA A UMA APLICAÇÃO
ISOMORFISMO
Dois grafos são isomórficos se for possível encontrar equivalência entre os rótulos/pesos das arestas mantendo-se as adjacências.
ISOMORFISMO
Dois grafos são isomórficos se for possível encontrar equivalência entre os rótulos/pesos das arestas mantendo-se as adjacências.
ISOMORFISMO
Dois grafos são isomórficos se for possível encontrar equivalência entre os rótulos/pesos das arestas mantendo-se as adjacências.
a = 1, b = 2
c = 3, d = 8
e = 5, f = 6
g = 7, h = 4.
ISOMORFISMO
ISOMORFISMO
CAMINHO
O caminho é uma sequência de vértices ou de arestas, onde cada elemento é adjacente ao anterior e ao posterior da sequência caso exista.
Sucessor: elemento seguinte a um determinado elemento do caminho.
Antecessor: elemento anterior a um determinado elemento do caminho.
Se existe um caminho entre dois vértices v1 e v2, dizemos que v1 alcança ou atinge v2 e vice-versa. 
CAMINHO
Caminho simples ou elementar é um caminho de vértices que não possui vértices repetidos.
Um trajeto ou trilha é um caminho de arestas que não possui arestas repetidas.
Comprimento é a quantidade de elementos do caminho.
Um caminho é ímpar se tiver comprimento ímpar e par e se tiver comprimento par.
CAMINHO
Caminho hamiltoniano, é um caminho simples entre todos os vértices de um grafo. 
Caminho euleriano, é o trajeto que contém todas as arestas de um grafo.
CAMINHO DE VALOR MÍNIMO 
Em grafos valorados é o caminho elementar entre dois vértices, cuja soma dos pesos é o mínimo
CAMINHO DE VALOR MÁXIMO
Em grafos valorados é o caminho elementar entre dois vértices, cuja soma dos pesos é o máximo
DISTÂNCIA
A distância entre dois vértices de um grafo é o menor comprimento dos caminhos entre esses dois vértices.
CICLO
Um ciclo é um caminho que inicia e termina em um mesmo elemento.
CICLO
Um grafo que não possui ciclo é chamado de acíclico. 
O menor ciclo do grafo é chamado de cintura e o maior ciclo é chamado de circunferência. 
Um grafo é uma gaiola se for regular em grau e possuir uma cintura.
CICLO
Uma aresta que une dois vértices não consecutivos de um ciclo é chamada de corda. 
É chamado de ciclo hamiltoniano, o ciclo simples entre todos os vértices de um grafo. 
É chamado de ciclo euleriano, o ciclo do trajeto que contém todas as arestas de um grafo. 
Um grafo, que contém um caminho euleriano e não possui um ciclo euleriano, é chamado de unicursal. 
CICLO FUNDAMENTAL
É UM CICLO SEM CORDAS
TEOREMAS E LEMAS
TEOREMA: ESTÁ PROVADO MATEMATICAMENTE QUE É VERDADE;
LEMA: NÃO FOI PROVADO, MAS É VERDADE PARA TODOS OS EXEMPLOS CONHECIDOS.
CONEXO
Um grafo G é conexo se e somente se, existir um caminho entre todos os pares de vértices do grafo G
Teorema 01: Um grafo G conexo possui ciclo euleriano se e somente se todos os vértices de G possuírem grau par.
OPERAÇÕES COM GRAFOS
Operações são equações feitas nos grafos. 
Algumas são aplicadas a apenas um grafo, essas são chamadas de unárias, outras são aplicadas a pares de grafos, a essas damos o nome de binárias. 
OPERAÇÕES COM GRAFOS
UNIÃO;
SOMA;
PRODUTO CARTESIANO (liga os iguais);
PRODUTO LEXOGRÁFICO (liga dos destinos);
SOMA DE ARESTAS;
CONTRAÇÃO;
DESDOBRAMENTO;
INCLUSÃO/EXCLUSÃO;
SUBGRAFO, SUPERGRAFO
UM GRAFO X É SUBGRAFO DE UM GRAFO Y SE TODOS OS VÉRTICES E ARESTAS DE X ESTIVEREM TAMBÉM EM Y.
UM GRAFO X É SUPERGRAFO DE UM GRAFO Y SE TODOS OS VÉRTICES E ARESTAS DE Y ESTIVEREM TAMBÉM EM X. 
X É SUBGRAFO PARCIAL DE Y SE FOR SUBGRAFO DE Y E TIVER TODOS SO VÉRTICES DE Y
PRÓPRIO
PRÓPRIO SIGNIFICA QUE NÃO É IGUAL.
TAMANHO
É A QUANTIDADE DE VÉRTICES E ARESTAS ESCRITAS NO FORMATO: N,M
MAXIMAL E MINIMAL
MAXIMAL É UM CONJUNTO ONDE NÃO É MAIS POSSÍVEL COLOCAR ELEMENTOS.
MINIMAL É UM CONJUNTO ONDE NÃO É MAIS POSSÍVEL RETIRAR ELEMENTOS.
NÃO CONFUNDIR COM MÁXIMO E MÍNIMO.
COMPONENTES CONEXOS
É A QUANTIDADE DE “PEDAÇOS” CONEXOS DE UM GRAFO.
COMPLETO
UM GRAFO COMPLETO É UM GRAFO ONDE TODOS OS VÉRTICES ESTÕA CONECTADOS E TODOS OS DEMAIS VÉRTICES DO GRAFO.
CHAMADOS DE K
Um grafo completo possui arestas
 =  binômio de Newton
COMPLETO
 K1	 K2		K3
		 K4 			 K5
COMPLEMENTO
O complemento de um grafo G é um grafo G’, onde G’ possui exatamente os mesmos vértices de G, porém, possui todas as arestas que não estão presentes em G, sendo que nenhuma aresta de G’ é igual a uma aresta de G.
A soma de arestas de G e G’ é um grafo completo.
BIPARTIDO
UM GRAFO É BIPARTIDO QUANDO SEUS VÉRTICES PODEM SER DIVIDIDOS EM DOIS GRUPOS DE VÉRTICES QUE NÃO SE TOCAM.
CADA CONJUNTO É CHAMADO DE CONJUNTO ESTÁVEL
BIPARTIDO
Teorema 02: Um grafo é bipartido se e somente se todo ciclo de G possuir comprimento par. 
BIPARTIDO COMPLETO
É UM GRAFO BIPARTIDO ONDE TODOS OS VERTICES DE UM GRUPO ESTÃO LIGADOS A TODOS OS VÉRTICES DO OUTRO GRUPO;
CHAMADOS DE KNG1,NG2
GARRA
É O K1,3
BIPARTIDO BALANCEADO
SE OS GRUPOS TIVEREM A MESMA QUANTIDADE DE VÉRTICES.
CLIQUE
SUBGRAFO PRÓPRIO COMPLETO DE UM GRAFO G QUALQUER.
CASO G SEJA COMPLETO, O CLIQUE É UM GRAU MENOR.
CLIQUE
CONJUNTO INDEPENDENTE DE VÉRTICES
UM SUBGRAFO PRÓPRIO DE UM GRAFO G, CUJOS VÉRTICES NÃO TEM LIGAÇÕES ENTRE SI.
COBERTURA
COBERTURA DE VÉRTICES: CONJUNTO DE VÉRTICES DE UM GRAFO G, ONDE TODOS OS DEMAIS VÉRTICES DE G SÃO ADJACENTES A PELO MENOS UM ELEMENTO DESTE CONJUNTO.
COBERTURA DE ARESTAS: CONJUNTO DE ARESTAS DE UM GRAFO G, ONDE TODAS AS DEMAIS ARESTAS DE G SÃO ADJACENTES A PELO MENOS UM ELEMENTO DESTECONJUNTO. 
ÁRVORES
UM GRAFO ACÍCLICO E CONEXO;
FOLHA: UM VÉRTICE DE GRAU MENOR OU IGUAL A 1 EM UMA ÁRVORE;
VÉRTICE INTERIOR: UM VÉRTICE DE GRAU MAIOR OU IGUAL A 2 EM UMA ÁRVORE;
FLORESTA: CONJUNTO DE ÁRVORES;
Teorema 03: Um grafo G é uma árvore se e somente se existir um único caminho entre cada par de vértices de G.
Teorema 04: Seja G(V, E) um grafo. As possíveis afirmativas são equivalentes:
G é uma árvore;
G é conexo e M é mínimo;
G é conexo e M = N – 1;
G é acíclico e M = N – 1;
G é acíclico e para todo v, w ϵ V, a adição da aresta (v, w) produz um grafo contendo exatamente um ciclo.
ELO
É UMA ARESTA QUE QUEBRA UM CICLO FUNDAMENTAL
POSTO É A QUANTIDADE DE ELOS, E É DADO POR M – N + 1
UM GRAFO CONEXO ONDE TODOS OS SEUS ELOS SÃO RETIRADOS, RESULTA EM UMA ÁRVORE. 
ARBORECÊNCIA
ÚMA ÁRVORE TEM ARBORESCÊNCIA SE UM DE SEUS VÉRTICES FOR ESCOLHIDO COMO RAIZ.
	
NÍVEL EM ÁRVORES
EM ÁRVORES ENRAIZADAS O NÍVEL DE UM VÉRTICE É A DISTÂNCIA EM ARESTAS DO VÉRTICE PARA A RAIZ.
A ALTURA DE UMA ÁRVORE É A DISTÂNCIA DA ÁRVORE PARA O VÉRTICE MAIS LONGE.
NÍVEL EM ÁRVORES
DE UM VÉRTICE V EM UMA ÁRVORE:
ANCESTRAL: QUALQUER VÉRTICE NO CAMINHO ENTRE V E A RAIZ; 
DESCENDENTE: QUALQUER VÉRTICE EM QUE V ESTÁ NO CAMINHO PARA A RAIZ
ANCESTRAL PRÓPRIO E DESCENDENTE PRÓPRIO: ANCESTRAL E DESCENDENTE QUE EXCLUI ELE MESMO;
NÍVEL EM ÁRVORES
FILHOS: DESCENDENTES DIRETOS DE V;
PAI: ASCENDENTE DITERO DE V;
IRMÃOS: TEM O MESMO PAI;
FOLHA: NÃO POSSUI FILHOS; 
EM UMA ÁRVORE ENRAIZADA, SE A ORDEM DOS FILHOS FOR IMPORTANTE ELA É UMA ÁRVORE ENRAIZADA ORDENADA;
SUBÁRVORE
ESCOLHE-SE UM OUTRO VÉRTICE PARA SER RAIZ E ELIMINA-SE QUEM NÃO FOR DESCENDENTE DESTE VÉRTICE EM RELAÇÃO A ÁRVORE ORIGINAL. O UQE SOBRA É A SUBÁRVORE.
A SUBÁRVORE É PARCIAL SE SE FALTAREM ALGUNS DESCENDENTES DO NOVO VÉRTICE ESCOLHIDO.
ÁRVORE M-ÁRIA
É UMA ÁRVORE EM QUE CADA VÉRTICE POSSUI, UM NÚMERO MÁXIMO DE FILHOS.
UNÁRIA, BINÁRIA, TERNÁRIA, QUATERNÁRIA,...
ÁRVORE ESTRITAMENTE M-ÁRIA
É UMA ÁRVORE EM QUE CADA VÉRTICE POSSUI, EXATAMENTE A MESMA QUANTIDADE DE FILHOS OU NENHUM.
ESTRITAMENTE UNÁRIA, ESTRITAMENTE BINÁRIA, ESTRITAMENTE TERNÁRIA, ESTRITAMENTE QUATERNÁRIA,...
ARBORICIDADE
QUANTIDADE MINIMAL DE COMPONENTES CONEXAS QUE SÃO ÁRVORES SEM REPETIR VÉRTICES DE UM GRAFO QUALQUER
ÁRVORE DE EXTENSÃO
É UMA ÁRVORE GERADA PELA RETIRADA DE TODOS OS ELOS DE UM GRAFO.
UMA ÁRVORE DE EXTENSÃO É ÁRVORE GERADORA DE UM GRAFO.
ÁRVORE DE EXTENSÃO
ÁRVORE DE EXTENSÃO
EXCENTRICIDADE
A EXCENTRICIDADE DE UM VÉRTICE V É A MENOR DISTÂNCIA, EM ARESTAS , DE V PARA O VÉRTICE MAIS LONGE.
O CENTRO DE UM GRAFO É O CONJUNTO DOS VÉRTICES DE MENOR EXCENTRICIDADE.
OS VÉRTICES QUE FAZEM PARTE DO CENTRO SÃO CHAMADOS DE CENTRÓIDE.
EXCENTRICIDADE
EXCENTRICIDADE
RAIO: A MENOR EXCENTRICIDADE DE UM GRAFO.
DIÂMETRO: A MENOR EXCENTRICIDADE DE UM GRAFO.
VÉRTICE PERIFÉRICO: É O VÉRTICE CUJA EXCENTRICIDADE É IGUAL AO DIÂMETRO DO GRAFO. 
Lema 01: Seja G uma árvore com pelo menos três vértices. Seja G’ a árvore obtida de G pela exclusão de todas as suas folhas. Então G e G’ possuem o mesmo centro.
Teorema 05: O centro de uma árvore G possui um ou dois vértices.
CORTE
CORTE DE VÉRTICE: CONJUNTO MINIMAL DE VÉRTICES QUE DESCONECTA O GRAFO.
O TAMANHO DO MENOR CORTE DE VÉRTICE DO GRAFO É CHAMADO CONECTIVIDADE DE VÉRTICE.
CORTE
CORTE DE ARESTAS: CONJUNTO MINIMAL DE VÉRTICES QUE DESCONECTA O GRAFO.
O TAMANHO DO MENOR CORTE DE VÉRTICE DO GRAFO É CHAMADO CONECTIVIDADE DE ARESTAS.
ARTICULAÇÃO
UM VÉRTICE QUE DESCONECTA O GRAFO
SCA: CONJUNTO, COM NO MÍNIMO 2 VÉRTICES QUE DESCONECTA O GRAFO.
SCAM: CONJUNTO MINIMAL, COM NO MÍNIMO 2 VÉRTICES QUE DESCONECTA O GRAFO.
ARTICULAÇÃO
PROCURE ARTICULAÇÃO
 E SCAM
ARTICULAÇÃO
CASO UM GRAFO G NÃO TENHA ARTICULAÇÃO E O MENOR SCAM DE G TENHA 2 ELEMENTOS ELE É CHAMADO BICONEXO.
PONTE
UMA ARESTA QUE DESCONECTA O GRAFO
EXTRACONECTIVIDADE
RETIRA-SE UM SUBGRAFO, SE OS COMPONENTES CONEXOS QUE SOBRAREM FOREM MAIORES QUE O SUBGRAFO, TEMOS A EXTRACONECTIVIDADE. 
BUSCA-SE O MINIMAL
BLOCO
SUBGRAFO K2
Lema 02: Seja G um grafo. Então:
(i) Cada aresta de G pertence a exatamente um bloco do grafo;
(ii) Um vértice v de G é articulação se e somente se v pertencer a mais de um bloco de G. 
Lema 03: Seja G(V, E) um grafo conexo, com |V| > 2. Então:
(i) Um vértice v do grafo é articulação de G se e somente se existirem, no grafo, vértices w, u ≠ v tais que v está contido em todo caminho entre w e u em G. 
(ii) Uma aresta (p, q) de G é ponte se e somente se (p, q) for o único caminho simples entre p e q em G.
Lema 04: Um grafo G(V, E), com |V| > 2, é biconexo se e somente se cada par de vértices de G está contido em algum ciclo.
Teorema 06: Seja G um grafo k-conexo, então existe algum ciclo de G passando por cada subconjunto de k vértices.
Teorema 07: Um grafo G(V, E) é k-conexo, se e somente se existissem k caminhos disjuntos (exceto nos extremos) entre cada par de vértices de G.
PLANARIDADE
UM GRAFO PLANAR PODE SER ESCRITO NO PLANO SEM CRUZAR ARESTAS
PLANARIDADE
UM GRAFO PLANAR PODE SER ESCRITO NO PLANO SEM CRUZAR ARESTAS
PLANARIDADE
SE UM GRAFO G FOR PLANAR, G É IMERSÍVEL NO PLANO
SE NÃO FOR POSSÍVEL DESENHAR SEM CRUZAR G É CHAMADO DE NÃO PLANAR
TODO GRAFO PLANAR PODE SER DESENHADO NA SUA REPRESENTAÇÃO PLANAR (SEM CRUZAR COM ARESTAS RETAS) 
PLANATIDADE
REPRESENTAÇÃO PLANAR?
FACES
AREAS DELIMITADAS POR ARESTAS. 
INCLUSIVE A FACE EXTERNA.
PERÍMETRO: VÉRTICES E ARESTAS QUE TOCAM A FACE EXTERNA.
PERIPLANAR: SE TODOS OS VÉRTICES ESTIVEREM NO PERÍMETRO DO GRAFO
FÓRMULA DE EULER
Teorema 08: Seja G um grafo planar, então 
n + f = m + 2
onde n é a quantidade de vértices, f é a quantidade de faces e m a quantidade de arestas.
Lema 05: Seja G um grafo planar, então m ≤ 3 n – 6, onde n é a quantidade de vértices e m a quantidade de arestas.
Lema 06: Os grafos K5 e K3,3 não são planares.
GÊNERO
É A QUANTIDADE DE FUROS NECESSÁRIA PARA DESENHAR UM GRAFO SEM CRUZAR.
SUBDIVISÃO
DIVIDIR UMA ARESTA EM VÁRIAS ARESTAS
Teorema 09: Um grafo é planar se e somente se não contiver, como subgrafo, uma subdivisão de K5 ou K3,3.
GRAFO HAMILTONIANO
POSSUI CICLO HAMILTONIANO
É BICONEXO EM VÉRTICES
Teorema 10: Seja G(V, E) um grafo hamiltoniano e S um subconjunto próprio de V, então o número de componentes conexos de G – S ≤ |S|, onde |S| é a quantidade de vértices de S. 
Teorema 11: Seja G(V, E) um grafo com pelo menos 3 vértices e tal que o grau (v) ≥ n / 2, para todo vértice v ϵ V, então G é hamiltoniano. 
COLORAÇÃO
PINTAR OS ELEMENTOS DO GRAFO COM A REGRA:
“ELEMENTOS ADJACENTES DEVEM POSSUIR CORES DIFERENTES”
VÉRTICES E ARESTAS
	
COLORAÇÃO
NÚMERO CROMÁTICO: MENOR QUANTIDADE DE CORES POSSÍVEL PARA PINTAR VÉRTICES DO GRAFO; 
ÍNDICE CROMÁTICO: MENOR QUANTIDADE DE CORES POSSÍVEL PARA PINTAR ARESTAS DO GRAFO; 
Teorema 12: Todo grafo planar, possui, no máximo, número cromático igual a 4.
Lema 07: Um grafo G(V, E) é bicolorível se e somente se for bipartido.
GRAFO MAPA
K-CRÍTICO
É UM GRAFO QUE QUANDO RETIRA QUALQUER ELEMENTO DIMINUE SEU NÚMERO CROMÁTICO.
Teorema 13: Se G(V, E) é k-crítico, 
então grau (v) ≥ k – 1, para todo v ϵ V.
Teorema 14: O índice cromático de um grafo é igual a delta ou a delta+1 (onde delta é o grau máximo do grafo). 
CLASSES DA 
COLORAÇÃO DE ARESTAS
Grafos com índice cromático igual a delta são classificados como Classe 1, os demais, são Classe 2. 
COLORAÇÃO HARMONIOSA
É A COLORAÇÃO MINIMAL DE VÉRTICES E ARESTAS SIMULTANEAMENTE, MANTENDO-SE A REGRA BÁSICA DA COLORAÇÃO.
EMPARELHAMENTO
CONJUNTO DE ARESTAS QUE TOCAM NO MÁXIMO POSSÍVEL DE VÉRTICES E NÃO SE TOCAM ENTRE SI.
EMPARELHAMENTO
CASO TOQUE EM TODOS OS VÉRICES, É CHAMADO DE EMPARELHAMENTO PERFEITO. 
SÓ É POSSÍVEL TER EMPARELHAMENTO PERFEITO EM GRAFOS PARES.
CAMINHO ALTERNANTE
É UM CAMINHO SIMPLES DE ARESTAS, ONDE CADA ELEMENTO DE ALTERNA ENTRA PERTENCER OU NÃO A UM EMPARELHAMENTO DO GRAFO.
CAMINHO AUMENTANTE
É UM CAMINHO ALTERNANTE QUE INICIA E TERMINAEM ELEMENTOS FORA DO EMPARELHAMENTO
CICLO ALTERNANTE
É UM CAMINHO ALTERNANTE QUE É UM CICLO.
BROTO
É UM CICLO ALTERNANTE DE COMPRIMENTO IMPAR.
BASE DO BROTO É O VÉRTICE DO BROTO QUE NÃO FAZ PARTE DO EMPARELHAMENTO.
AS ARESTAS DO BROTO SÃO CHAMADAS DE TALO DO BROTO.
COCICLO
CONJUNTO DE ARESTAS QUE COMPÕE UM CICLO ALTERNANTE OU UM BROTO.
DÍGRAFOS
EVOLUÇÃO DOS GRAFOS.
TODO DÍGRAFO É UM GRAFO, O CONTRÁRIO NÃO É VERDADE.
AS ARESTAS DE UM DÍGRAFO SÃO SETAS.
DÍGRAFOS
CONVERGENTE: VÉRTICE QUE É APONTADO POR UMA ARESTA.
DIVERGENTE: VÉRTICE DE ONDE PARTE UMA ARESTA.
CIRCUITO
É UM CICLO EM DÍGRAFOS.
Lema 08: Todo dígrafo acíclico possui, pelo menos, uma fonte e um sumidouro
COCIRCUITO
COCICLO EM DÍGRAFOS.
GRAU DE ENTRADA E DE SAÍDA
GRAU DE ENTRADA: QUANTIDADE DE ARESTAS QUE CONVERGEM (ENTRAM) DO GRAFO.
GRAU DE SAÍDA: QUANTIDADE DE ARESTAS QUE DIVERGEM (SAEM) DO GRAFO.
FONTE E SUMIDOURO
UMA FONTE DE UM DÍGRAFO É UM VÉRTICE CUJO GRAU DE ENTRADA É IGUAL ZERO. 
UM SUMIDOURO DE UM DÍGRAFO É UM VÉRTICE CUJO GRAU DE SAÍDA É IGUAL A ZERO
SUBJACENTE
O SUBJACENTE D EUM DÍGRAFO É O GRAFO GERADO A PARTIR DESDE DÍGRAFO TRANSFORMANDO SUAS SETAS EM ARESTAS SIMPLES.
ALCANÇÁVEL
DIZEMOS QUE UM VÉRTICE ALCANÇA OUTRO SE EXISTE UM CAMINHO ENTRE ELES.
FORÇAS DE CONEXÃO
FORTEMENTE CONEXO: TODOS OS VÉRTICES ALCANÇAM TODOS;
FORÇAS DE CONEXÃO
UNILATERALMENTE CONEXO: EXISTE UM VÉRTICES QUE ALCANÇA TODOS;
FORÇAS DE CONEXÃO
FRACAMENTE CONEXO: EXISTE UM VÉRTICES QUE ALCANÇA TODOS;
FORÇAS DE CONEXÃO - CATEGORIAS
C3, se for fortemente conexo;
C2, se for unilateralmente conexo e não for fortemente conexo;
C1, se for simplesmente conexo e não for unilateralmente conexo;
C0, se for desconexo.
FORMA CANÔNICA
UM DÍGRAFO ESTÁ NA FORMA CANÔNICA SE, QUANDO CRIARMOS SETAS DE TODOS OS SUMIDOUROS PARA TODAS AS FONTES, ESTE DÍGRAFO TORNAR-SE FORTEMENTE CONEXO.
FECHO TRANSITIVO
PARA CADA VÉRTICE V DE UM DÍGFRAFO, DEVEMOS INCLUIR ARESTAS (SETAS) DIRETAS PARA TODOS OS VÉRTICES ALCANÇÁVEIS POR V (FECHO TRANSITIVO DIRETO DE V). 
O CONJUNTO DOS VÉRTICES ALCANÇÁVEIS POR V É CHAMADO DE FECHO TRANSITIVO DIRETO DE V.
O CONJUNTO DOS VÉRTICES QUE ALCANÇA V É CHAMADO DE FECHO TRANSITIVO INVERSO DE V.
FECHO TRANSITIVO
FECHO TRANSITIVO DIRETO:
1:
2:
3:
4:
5:
6:
2, 3, 4, 5, 6
4, 5, 6
5
λ
λ
5
 
FECHO TRANSITIVO
FECHO TRANSITIVO INVERSO:
1:
2:
3:
4:
5:
6:
λ
1
1
1, 2
1, 2, 3, 6
1, 2
 
REDUÇÃO TRANSITIVA
É A RETIRADA MAXIMAL DE ARESTAS, MANTENDO-SE O FECHO TRANSITIVO DIRETO DE TODOS OS VÉRTICES. 
REDUÇÃO TRANSITIVA
FECHO TRANSITIVO DIRETO:
1:
2:
3:
4:
5:
6:
7:
8:
2, 3, 4, 5, 6, 7, 8
3, 4, 5, 6, 7, 8
4, 5, 6, 7, 8
 
5, 6, 7, 8
6, 7, 8
7, 8
8
λ
REDUÇÃO TRANSITIVA
FECHO TRANSITIVO DIRETO:
1:
2:
3:
4:
5:
6:
7:
8:
2, 3, 4, 5, 6, 7, 8
3, 4, 5, 6, 7, 8
4, 5, 6, 7, 8
 
5, 6, 7, 8
6, 7, 8
7, 8
8
λ
REDUÇÃO TRANSITIVA
FECHO TRANSITIVO DIRETO:
1:
2:
3:
4:
5:
6:
7:
8:
2, 3, 4, 5, 6, 7, 8
3, 4, 5, 6, 7, 8
4, 5, 6, 7, 8
 
5, 6, 7, 8
6, 7, 8
7, 8
8
λ
ORDENAÇÃO PARCIAL
SUPOR QUE C SEJA O CONJUNTO {1, 2, 3} E X, Y, Z ELEMENTOS QUALQUER DESSE CONJUNTO . VAMOS AS AFIRMAÇÕES:
X ≤ X, para X ϵ C?
X ≤ Y e Y ≤ X  X = Y, para X e Y ϵ C?
X ≤ Y e Y ≤ Z  X ≤ Z, para X, Y e Z ϵ C? 
REFLEXIVO
ANTI-SIMÉTRICO
TRANSITIVO
ORDENAÇÃO PARCIAL
SUPOR QUE C SEJA O CONJUNTO {1, 2, 3} E X, Y, Z ELEMENTOS QUALQUER DESSE CONJUNTO . VAMOS AS AFIRMAÇÕES:
X < X, para X ϵ C? 
X < Y então Y < X, para X e Y ϵ C?
X ≤ Y e Y ≤ Z  X ≤ Z, para X, Y e Z ϵ C? 
IRREFLEXIVO
ASSIMÉTRICO
TRANSITIVO
ORDENAÇÃO PARCIAL
SE UM CONJUNTO FOR REFLEXIVO, ANTI- SIMÉTRICO E TRANSITIVO OU 
IRREFLEXIVO, ASSIMÉTRICO E TRANSITIVO: 
DIZEMOS QUE ELE É UMA ORDENAÇÃO PARCIAL E PODENDO SER ORDENADO.
APENAS GRAFOS NO SEU FECHO TRANSITIVO FORMAM UMA ORDENAÇÃO PARCIAL, OU SEJA, INDUZ UM CONJUNTO PARCIALMENTE ORDENADO. 
ÁRVORE DIRECIONADA 
UM DÍGRAFO D
UM ÚNICO VÉRTICE R, DENOMINADO DE RAIZ, COM GRAU DE ENTRADA IGUAL A ZERO
TODOS OS DEMAIS VÉRTICES TEM GRAU DE ENTRADA IGUAL A 1. 
D É CONEXO E ACÍCLICO E SEU SUBJACENTE TAMBÉM.
ENTÃO D TEM ARBORESCÊNCIA
SUBCONJUNTOS ESTÁVEIS
SUBCONJUNTO INTERNAMENTE ESTÁVEL – SCIE
CONJUNTO DE VÉRTICES QUE NÃO SE TOCAM.
SUBCONJUNTOS ESTÁVEIS
SUBCONJUNTO EXTERNAMENTE ESTÁVEL – SCEE
EM UM DÍGRAFO, É O CONJUNTO DE VÉRTICES EM QUE TODOS OS DEMAIS APONTAM PARA PELO MENOS DO CONJUNTO.
SUBCONJUNTOS ESTÁVEIS
SE UM CONJUNTO FOR AO MESMO TEMPO SCIE E SCEE, ELE É NÚCLEO DO GRAFO.
SE UM SCIE FOR SCAM, OU SEJA, DESCONECTAR O GRAFO, ENTÃO O GRAFO É FRÁGIL. 
Teorema 15: Todo núcleo é, ao mesmo tempo, um SCIE maximal e um SCEE minimal.
Teorema 16: Todo dígrafo, sem circuitos, possui um núcleo único.
ESPESSURA
MENOR NÚMERO DE SUBGRAFOS PLANARES, QUE NÃO POSSUEM ARESTAS EM COMUM.
ESPESSURA* ≡ m 		
		 (3n – 6)
* QUALQUER PARTE DECIMAL ARREDONDA PARA MAIS.
SIMETRIA
SIMÉTRICO: QUANDO PARA TODA ARESTA QUE DIVERGE, TEM OUTRA QUE CONVERGE NA MESMA DIREÇÃO E SENTIDO OPOSTO.
Um grafo não orientado é sempre simétrico
SIMETRIA
ANTI-SIMÉTRICO: SE PARA TODA ARESTA QUE CONVERGE, NUNCA EXISTE UMA DIVERGENTE NA MESMA DIREÇÃO E SENTIDO CONTRÁRIO
SIMETRIA
PSEUDO-SIMÉTRICO: SE O GRAU DE ENTRADA FOR IGUAL AO GRAU DE SAÍDA PARA TODO VÉRTICE; 
Teorema 17: Um dígrafo conexo possui um circuito euleriano se e somente se for pseudo-simétrico.
Teorema 18: Em um grafo planar maximal com mais de 4 vértices, o conjunto de vértices de grau 3 é um SCIE.
BASE E ANTI-BASE
BASE: É UM SCIE QUE ALCANÇA TODOS OS VÉRTICES;
ANTI-BASE: UM SCIE QUE É ALCANÇADO POR TODOS OS VÉRTICES
BASE E ANTI-BASE
CONJUNTO FUNDAMENTAL E ANTI-FUNDAMENTAL
Um conjunto fundamental é o fecho transitivo direto de um vértice de uma base. 
Um conjunto anti-fundamental é o fecho transitivo inverso de um vértice de uma anti-base.
ONORÍFICO
N<= 8
M = 7
É UM DÍGRAFO
ENRAIZADO
COM CAMINHO 
EULERIANO A PARTIR DA RAIZ
TRIANGULAÇÃO
UMA TRIANGULAÇÃO É UM GRAFO PLANAR CONEXO NO QUAL TODAS AS FASES, EXCETO A FACE EXTERNA SÃO COMPOSTAS POR TRIÂNGULOS.
TRIANGULAÇÃO
CÁPSULA
É UMA TRIANGULAÇÃO NA QUAL O NÚMERO DE VÉRTICES DE GRAU 3 INTERNOS É MAIOR OU IGUAL AO NÚMERO DE VÉRTICES RESTANTES.
TRIÂNGULO SEPARADOR
É um triângulo que não é face em uma triangulação. 
Uma triangulação que não existe triângulo separador é chamada de NST-Triangulação. 
 
TRIÂNGULO SEPARADOR
Todo grafo planar maximal, que seja uma triangulação e que não tenha um triângulo separador, possui ciclo hamiltoniano.
 
GRAFO DE ARESTAS
É UM GRAFO G’ GERADO A PARTIR DE OUTRO G ONDE TODAS AS ARESTAS DE G SÃO VÉRTICES DE G’ E AS ADJACÊNCIAS DE G SÃO AS ARESTAS DE G’.
GRAFO DUAL
É UM GRAFO G’ GERADO A PARTIR DE OUTRO G ONDE TODAS AS FACES DE G SÃO VÉRTICES DE G’ E AS FRONTEIRAS DE G SÃO AS ARESTAS DE G’.
GRAFOS PERFEITOS
UM GRAFO G É DITO PERFEITO SE E SOMENTE SE NEM G, NEM O COMPLEMENTO DE G CONTIVEREM UM CICLO ÍMPAR DE COMPRIMENTO MAIOR QUE 3 COMO SUBGRAFO. 
UM GRAFO É CRITICAMENTE IMPERFEITO SE NÃO FOR PERFEITO, MAS TODOS OS SEUS SUBGRAFOS PRÓPRIOS FOREM PERFEITOS. 
PANCÍCLICO
UM GRAFO G É PANCÍCLICO SE POSSUIR CICLOS DE TODOS OS COMPRIMENTOS POSSÍVEIS A PARTIR DE 3, ATÉ SUA QUANTIDADE DE VÉRTICES. 
PANCÍCLICO
PANCÍCLICO EM VÉRTICES SE CADA VÉRTICE PERTENCER A, PELO MENOS, UM CICLO DE CADA TAMANHO. 
PANCÍCLICO
PANCÍCLICO EM ARESTAS SE CADA ARESTA PERTENCER A, PELO MENOS, UM CICLO DE CADA TAMANHO. 
FRACAMENTE PANCÍCLICO
SE POSSUIR UM CICLO DE CADA TAMANHO, ENTRE SUA CINTURA E SUA CIRCUNFERÊNCIA.
REPRESENTAÇÃO ALGORITMICA
A REPRESENTAÇÃO ESQUEMÁTICA NÃO É ADEQUADA PARA FORNECER A UM COMPUTADOR DADOS SOBRE A ESTRUTURA DE UM GRAFO, POR ISSO, PESQUISADORES DESENVOLVERAM FORMAS DE REPRESENTAÇÃO QUE ATENDEM A NECESSIDADES ALGÉBRICAS OU COMBINATÓRIAS, DENTRO DE ESTRUTURAS DE DADOS, PARA ARMAZENAMENTO E USO EM ALGORITMOS
REPRESENTAÇÃO ALGORITMICA
LISTA DE ADJACÊNCIA
GRAFO: TABELA COM 2 COLUNAS: ORIGEM E DESTINO
DÍGRAFO: TABELA COM 2 COLUNAS: VÉRTICE E QUEM ATINGE O VÉRTICE DA COLUNA1 
MATRIZ DE ADJACÊNCIA
COMPOSTA POR UMA MATRIZ N X N, ONDE AS LINHAS REPRESENTAM O VÉRTICE DE ORIGEM E AS COLUNAS O VÉRTICE DE DESTINO.
COLOCA-SE 1 QUANDO TIVER LIGAÇÃO E 0 QUANDO NÃO TIVER.
MATRIZ DE INCIDÊNCIA
COMPOSTA POR UMA MATRIZ N X M
CADA LINHA REPRESENTA UM VÉRTICE
CADA COLUNA, UMA ARESTA. 
ARESTA SAI DO VÉRTICE: + 1
ARESTA CHEGA NO VÉRTICE: – 1
ESTRUTURA DE ADJACÊNCIA
É UM VETOR COM N ELEMENTOS, ONDE CADA ELEMENTO É UM A LISTA ESCADEADA. 
CADA ELEMENTO DA LISTA É UM VÉRTICE APONTADO PELO ELEMENTO DO VETOR.
MATRIZ LAPLACIANA
É A MATRIZ DE ADJACÊNCIA, PORÉM:
AO INVÉZ DE “1”, COLOCA-SE “-1” QUANDO HOUVER LIGAÇÃO;
A DIAGONAL PRINCIPAL POSSUI O GRAU DO VÉRTICE.
MATRIZ FIGURATIVA
É A MATRIZ DE ADJACÊNCIA, PORÉM, AO INVÉS DE 1, PINTA-SE O ESPAÇO DA MATRIZ, COMO UM MAPA DE PIXELS E DEIXA EM BRANCO AO INVÉS DO ZERO.
“CANICHE” DE KAUFMANN
AUTOMORFIMO
UM GRAFO G ONDE, EM SUA MATRIZ DE AJDACÊNCIA, AS ORDENS DAS LINHAS PODEM SER EMBARALHADAS (COLUNAS ACOMPANHAM AS LINHAS), E G NÃO MUDA.
JOGOS EM GRAFOS
MUITOS JOGOS SÃO BASEADOS EM GRAFOS;
POLÍCIA-E-LADRÃO
JOGOS EM GRAFOS
MILHARES
JOGOS EM GRAFOS
GRAFOS DE CENA
É A MODELAGEM DE UMA CENA, GERALMENTE 3D, UTILIZANDO GRAFOS.
DEFINE, NO MÍNOMO, ONDE SERÃO POSICIONADOS OS OBJETOS TANTO FISICAMENTE QUANTO LOGICAMENTE.
CADA VÉRTICE PODE DEFINIR: FORMATO, PROPRIEADES OU GRUPO DE OBJETOS.
GRAFOS DE CENA
PROBLEMAS EM GRAFOS
PROBLEMA DAS PONTES DE KÖNIGSBERG
PROBLEMAS EM GRAFOS
PROBLEMA DO SCIE. CONSISTE EM ENCONTRAR O SUBCONJUNTO INTERNAMENTE ESTÁVEL MAXIMAL DE UM GRAFO G. 
PROBLEMA DO ISOMORFISMO EM GRAFOS. CONSISTE EM SABER SE DOIS GRAFOS SÃO OU NÃO ISOMÓRFICOS ENTRE SI. 
PROBLEMA DA COLORAÇÃO EM GRAFOS. CONSISTE EM DESCOBRIR QUAL É A COLORAÇÃO MÍNIMA DE UM GRAFO G.
 
 
PROBLEMAS EM GRAFOS
Problema do Clique. Consiste em, dado um grafo G e uma constante natural positiva k, decidir se existe um clique de tamanho ≥ k em G.
Problema da Satisfabilidade (SAT). É um problema de lógica que envolve expressões booleanas. Com uma expressão booleana na sua forma normal conjuntiva (FNC), decidir se a expressão é satisfatível, ou seja, verificar se existe uma atribuição de valores às variáveis da expressão de tal modo que a expressão seja avaliada verdadeira.
PROBLEMAS EM GRAFOS
Problema da Cobertura. Consiste em, dado um grafo G e uma constante natural positiva k, decidir se existe uma cobertura de tamanho ≤ k em G.
Problema do Ciclo Hamiltoniano. Saber se um grafo G possui ou não um ciclo hamiltoniano.  
Problema da Parada. Consiste em se decidir, para qualquer algoritmo A e qualquer entrada de A, se A vai terminar ou entrar em loop infinito. 
 
PROBLEMAS EM GRAFOS
PROBLEMA DA ÁRVORE DE EXTENSÃO MÍNIMA. EM UM GRAFO VALORADO, CONSISTE EM DESCOBRIR QUAL É A ÁRVORE DE EXTENSÃO COM MENOR VALOR NO GRAFO. 
PROBLEMA DO CAMINHO MÍNIMO. EM UM GRAFO VALORADO G, CONSISTE EM DESCOBRIR O MENOR CAMINHO ENTRE DOIS VÉRTICES QUALQUER DE G.
PROBLEMAS EM GRAFOS
Problema do Carteiro Chinês. Um carteiro que deve percorrer um roteiro todo dia. O problema é de identificar esse roteiro de maneira a minimizar a distância total percorrida. Essa situação pode ser representada por um grafo onde as arestas correspondem às ruas e os vértices correspondem aos cruzamentos.
Problema do Caixeiro Viajante. É um problema de otimização. Um dos mais investigados, por cientistas, matemáticos e investigadores de diversas áreas, tais como: logística, genética e produção, entre outros. Consiste na procura de um ciclo ou circuito que possua a menor distância, começando numa cidade (vértice) qualquer, entre várias, visitando cada cidade precisamente uma vez e regressando à cidade inicial. 
PROBLEMAS EM GRAFOS
Problema do Passeio do Cavalo do Xadrez. O Cavalo é a única peça do xadrez que pode saltar sobre outras peças. Ele tem um movimento bem peculiar em formato de "L": duas casa no sentido vertical ou horizontal e uma casa no outro sentido. Seguindo as regras de movimentação do cavalo, é possível que um cavalo parta de uma casa qualquer, do tabuleiro de xadrez, percorra todo o tabuleiro visitando cada casa uma e somente uma única vez e retorne à casa inicial? 
PROBLEMAS EM GRAFOS
Problema do Passeio do Cavalo do Xadrez. 
PROBLEMAS EM GRAFOS
Problema das Cinco Damas. A dama pode mover-se tantas casas quantas quiser em qualquer direção vertical, horizontal ou diagonal, desde que não haja nenhuma outra peça que obstrua sua passagem. Todas as casas que a dama alcança estão sob seu domínio. Qualquer outra peça que estiver numa casa sob domínio da dama estará sob seu ataque. Este problema consiste em procurar as posições a serem ocupadas por damas em um tabuleiro de xadrez vazio, de modo que elas possam controlar todas as casas do tabuleiro com o menor número de damas possível. 
PROBLEMAS EM GRAFOS
Problema das Oito Damas. A dama pode mover-se tantas casas quantas quiser em qualquer direção vertical, horizontal ou diagonal, desde que não haja nenhuma outra peça que obstrua sua passagem. Todas as casas que a dama alcança estão sob seu domínio. Qualquer outra peça que estiver numa casa sob domínio da dama estará sob seu ataque. Este problema consiste em descobrir quantas maneiras há de se colocar 8 damas em um tabuleiro de xadrez de forma que nenhuma dama ameace a outra.
PROBLEMAS EM GRAFOS
Problema do Desenho da Casa. No desenho, uma criança diz ter posto a ponta do lápis numa das bolinhas e com movimentos contínuos (sem levantar o lápis e sem sobrepor linhas) traçou as linhas que formam o desenho da casa, traçando cada linha uma única vez. Isso é possível?
PROBLEMAS EM GRAFOS
Problema dos Conspiradores Políticos. Os agentes A, B, C, D, E, F, G e H são conspiradores políticos. De forma a coordenar seus esforços, é vital que cada agente seja capaz de comunicar-se direta ou indiretamente com todos os outros conspiradores. Esta comunicação, contudo, envolve um certo risco para cada um. Os fatores de risco associados à comunicação direta entre cada par de conspiradores é dado por:
Todas as outras comunicações diretas são impraticáveis, pois exporiam todo o esquema de disfarce. Qual é o menor risco total envolvido neste sistema de conexão, ou seja, o menor risco para que uma mensagem seja repassada para todos os conspiradores?
	A 	A 	A 	A 	A 	B 	B 	C 	C 	C 	C 	D 	D 	E 
	B 	C 	E 	F 	G 	C 	F 	D 	F 	G 	H 	E 	H 	H 
	9 	3 	8 	3 	4 	10 	6 	6 	4 	5 	7 	6 	3 	5
PROBLEMAS EM GRAFOS
Problema do Metrô. Considere a rede de metrô de uma cidade como Paris, na França. Esta rede cobre boa parte da cidade, sendo composta por várias linhas que se cruzam em estações específicas. Nestes pontos de cruzamento um usuário pode livremente sair de uma composição e passar para uma composição de outra linha. Sendo assim, em geral o usuário tem mais de uma opção de rota quando deseja deslocar-se de uma parte a outra da cidade. Escolher a melhor rota passa, então, a ser fundamental para que o deslocamento seja o mais rápido possível. As distâncias entre estações vizinhas do metrô não são iguais e, consequentemente, o tempo de deslocamento entre estações vizinhas não é constante. Estas diferenças de tempo não são, contudo, significativas quando comparadas com os tempos de parada das composições nas estações e de troca de composição (de linha). Em redes de metrô de várias cidades do mundo há sistemas computacionais, que utilizam grafos, para auxiliar os usuários a escolher a melhor rota para um deslocamento particular. Mais do que simplesmente indicar uma rota possível, este problema consistem em identificar aquela rota que conduz o usuário o mais rapidamente ao seu destino. Dois critérios básicos para esta escolha são (em ordem de importância): procurar minimizar o número de trocas de composição (de linhas) e procurar minimizar o número de paradas em estações.
PROBLEMAS EM GRAFOS
PROBLEMAS EM GRAFOS
Problema da Organização dos Horários. Em uma universidade, temos vários cursos que funcionam de segunda a sexta, nos turnos de manhã, tarde e noite. Alguns cursos possuemquatro anos de duração, outros cinco anos. Os professores, que dão aulas em vários cursos, também trabalham em outras instituições, porém, possuem uma disponibilidade de horário suficiente para atender suas disciplinas com folga naquela universidade. Os cursos são divididos em semestres, e, para cada semestre, os cursos têm cinco disciplinas específicas para disponibilizar. O problema consiste em montar o horário escolar para atender todos os cursos, de maneira que não haja choque de horário em disciplinas de um mesmo semestre e turno, e que atenda a disponibilidade dos professores, sem que haja choque de horário entre as disciplinas que irá ministrar. 
PROBLEMAS EM GRAFOS
Problema dos Canibais e dos Missionários. Três canibais e três missionários estão viajando juntos e chegam a um rio. Eles desejam atravessar o rio, sendo que o único meio de transporte disponível é um barco que comporta no máximo duas pessoas. Há uma outra dificuldade: em nenhum momento, o número de canibais pode ser superior ao número de missionários, pois desta forma, os missionários estariam em grande perigo de vida. O problema consiste em administrar a travessia do rio, de maneira que todos atravessem sem deixar algum missionário correndo risco de vida. 
PROBLEMAS EM GRAFOS
Problema dos Três Maridos Ciumentos. Três esposas e seus respectivos maridos desejam ir ao centro da cidade em um Corvette, o qual comporta apenas duas pessoas. Como eles poderiam deslocar-se até o centro considerando que nenhuma esposa deveria estar com um ou ambos os outros maridos a menos que seu marido também esteja presente?
PROBLEMAS EM GRAFOS
Problema da Telefonia Celular. A empresa de telefonia celular Tabajara pretende se instalar em Petrolina. A empresa considera importante que todo o perímetro a cidade esteja coberta por sinal de telefonia celular, de forma que em qualquer ponto do território municipal (urbano, rural, projetos e distritos) um usuário possa obter sinal e falar normalmente. Isto significa distribuir diversas antenas de telefonia celular, porém, dado que o custo de instalação de uma antena é relativamente alto, a empresa solicita ao departamento técnico um estudo para identificar o menor número de antenas (com as correspondentes localizações aproximadas) necessárias para realizar esta cobertura. 
PROBLEMAS EM GRAFOS
Problema dos Potes de Vinho. Considere que temos três potes com capacidades de 8, 5 e 3 litros, respectivamente, os quais não possuem qualquer marcação. O maior deles está completamente cheio enquanto que os outros dois estão vazios. O problema consiste em dividir o vinho em duas porções iguais de 4 litros, tarefa esta que pode ser realizada por transvasos sucessivos de
um vaso no outro. Qual o 
menor número de transvasos 
necessários para completar a 
divisão?
CADEIA
Uma cadeia é uma sequência qualquer de arestas sucessivamente adjacentes que ligam dois vértices, tornando-se um caminho entre estes dois vértices.
PROPRIEDADES DA CADEIA
Elementar: é uma cadeia que não passar duas vezes pelo mesmo vértice. 
Exemplos de cadeias elementares: {5 7}, {0}, {3 8 9}, {1 3 5}
Exemplos de cadeias não elementares: {1 2}, {3 4}, {3 5 6}, {1 3 4 3 5 7} 
 
Simples: é uma cadeia que não passa duas vezes pela mesma aresta.
Exemplos de cadeias simples: {1 2 3 5 7}, {0}, {3 5 6}, {3 4}, {1 3 8 9}
Exemplos de cadeias não simples: { 2 2 3}, {1 2 3 4 3 5 6 7}, {1 2 3 4 3 5 6 6 7} 
 
PROPRIEDADES DA CADEIA
Tamanho ou Comprimento |c|: é a quantidade de arestas que compõe a cadeia. Exemplos: 
c = {1 2 3 5 7}  |c| = 5;
c = {0}  |c| = 1
c = {3 8 9}  |c| = 3;
c = {1 2 2 3}  |c| = 4;
c = {4 3 5 6 7}  |c| = 5;		
c = {3 4 3 5 6 6 7}  |c| = 7;
PROPRIEDADES DA CADEIA
Concatenação //: é a unificação de cadeias. Só será permitido concatenar uma cadeia c1 com uma cadeia c2 se a última aresta da cadeia c1 for adjacente a primeira aresta da cadeia c2. Exemplo: 
c1 = {1 2 3 4 3},	c2 = {5 6 6 6 7}	
c1 // c2 = {1 2 3 4 3 5 6 6 6 7}	
 
Atenção: a concatenação não é uma propriedade comutativa, ou seja: c1 // c2 ≠ c2 // c1.
PROPRIEDADES DA CADEIA
Sucessor: é o elemento seguinte a um elemento qualquer da cadeia.
Exemplo:
Na cadeia c = {1 2 3 5 6 6 7}, podemos dizer que 3 é sucessor de 2, mas não é sucessor de 1, pois 3 aparece logo após 2 e não logo após 1. 
 
Antecessor: é o elemento anterior a um elemento qualquer da cadeia.
Exemplo:
Na cadeia c = {1 2 3 5 6 6 7}, podemos dizer que 3 é antecessor de 5, mas não é antecessor de 6, pois 3 aparece logo antes de 5 e não de 6. 
PROPRIEDADES DA CADEIA
Reversa : é a cadeia escrita de trás para frente. Esta propriedade é comum apenas em grafos não orientados, pois, em dígrafos, a reversão da cadeia entre os vértices v e w, poderá não resultar em um caminho entre w e v. 
Exemplo:
c = {1 2 3 5 6 6 7}		c = {7 6 6 5 3 2 1}
 
PROPRIEDADES DA CADEIA
Elemento Neutro λ: é um elemento que concatenado com uma cadeia, resulta na própria cadeia, ou seja: c // λ = λ // c = c. 
Exemplo:
c = {1 2 3 5 6 6 7}		
c // λ = {1 2 3 5 6 6 7} // λ = {1 2 3 5 6 6 7}
PROPRIEDADES DA CADEIA
Validação: sejam dois vértices v, w de um grafo, onde v é a raiz e w um vértice marcado como validador (ou final). Uma cadeia é dita válida em um grafo, se for um caminho entre v e w.
 
Exemplo (considerando v7 como vértice validador):
c = {1 2 2 2 3 4 2 2 3 5 6 6 6 7} é uma cadeia válida entre os vértices v1 e v7.
PROPRIEDADES DA CADEIA
Fecho: o fecho é um ciclo, em um grafo, que permite cadeias de comprimento que tende ao infinito.
Exemplo: temos os fechos: {2}, {3, 4} e {6}, permitindo a existência de cadeias, como:
c = {1 2 2 2 ... 2 3 5 6 7}	c = {1 3 4 3 4 3 4 3 4 ... 3 4 3 5 6 6 ... 6 6 7}
 
Quando as arestas que compõe um fecho puderem ser totalmente excluídas da cadeia, de maneira que mantenha a validação da mesma, chamamos esse fecho de fecho estrela *. Caso contrário, temos um fecho positivo +. Os fechos {2} e {6} são fechos estrela e o fecho {3, 4} é positivo. Com isso, podemos representar as cadeias do exemplo, da seguinte maneira: 
c = {1 2* 3 5 6 7} e c = {1 (3 4)+ 3 5 6* 7}
DÚVIDAS