Conceitos Básicos de Grafos

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Um grafo simples de n vétices tem no máximo n x (n-1)/2 arestas
grafo completo é um grafo simples em que todo par de vértices é adjacente ( um grafo completo de n vétices é denotado por Kn).
grafo vazio é um grafo onde nenhum par de vértices é adjacente
um caminho é um grafo simples cujos vértices podem ser listaods em uma sequencia linear de tal forma que dois vétices são adjacentes se e somente se são consecutivos na sequência.
Caminho de vértices denotado por Pn.
Um ciclo é um grafo simples com 3 ou mais vértices que são listados em uma sequencia ciclica de tal forma que dois vértices só são adjacentes se e somente se são consecutivos na sequência.
porque grafos com 1 ou 2 vétices não são ciclicos? Porque não são simples. com 1 vértice possui um laço e com 2 vétices possui arestas paralelas.
Um grafo ciclico de n vértices é denotado por Cn.
O comprimento de um ciclo ou caminho é dado pelo número de arestas. (comprimento de um caminho Pn é N-1 e um ciclo Cn tem comprimento n.
caminho ou ciclo de comprimento k é chamado k-caminho ou k-ciclo
um caminho ou cilco é impar ou par dependendo da paridade de seu comprimento.
Um grafo é conexo se quando uma partição de V em dois gruos X e Y há uma aresta com extremos em X e outro em Y; Caso contrário é desconexo.
matriz de incidência(vértices e arestas) e matriz de adjacencia (vértices)
grafos bipartidos são aqueles que quandoseus vétices são divididos em dois conjuntos, toda aresta do grafo tem um extremo em cada um dos conjuntos.
Se um grafo é simples e todo vértice é adjacente a todo vértice deizemos que é um grafo bipartido completo.
um caminho pode ser bipartido
um grafo completo pode ser bipartido
um ciclo não pode ser bipartido
Grau de um vértice é o número de arestas que incidem no vértice, sendo cada laço contado duas vezes
vértice de grau zro é chamado vértice isolado
grau mínimo, vértice com menor incidência(sigma G)
grau máximo, vértice com maior incidência(delta G)
Dms: Seja M a matriz de incidência de G.
A soma dos valores na linha relativa a v é d(v).
Assim, somatória v?V d(v) é a soma de todas as entradas de M.
A soma dos valores de cada coluna é 2, pois cada aresta tem
2 extremos.
Portanto a soma de todas as entradas de M também é 2m.
O número de vértices de grau ímpar é par.
grafos orientados:
grafos que dominam = vizinhos de entrada
os grafos dominados= vizinhos de saída
arcos paralelos são aqueles com mesmo par de origem e destino
grafos direcionados estritos são aqueles sem laços nem arcos paralelos
quando a orientação dos arcos é irrelevante ou desconhecida podemos chamá-los de arestas
Isomorfismo
dois grafos são identicos se contem a mesma quantidade de vértices e de arestas e possui mesma incidencia
podem ser representadas com o mesmo desenho
há grafos que são muito parecidos, e diferem apenas no rótulo. Apesar de não identicos possui mesma estrutura e são chamos de isomorfos.
dizemos que há isomorfismo se há bijeção nas funções de incidência de vértices, preservando as adjacencias
ter o mesmo numero de vértices e arestas é fundamental para que ocorra isomorfismo, além disso, é necessario que ter o mesmo númoro de vértice de grau k para todo k.
Se dois grafos são isomorficos ou eles são identicos ou se diferem apenas nos rótulos, porém possuem a mesma estrutura
Na maior parte estamos interessados nas propriedades estruturais do grafo
definimos um grafo não rotulado com um representante qualquer de sua classe de equivalência
Um grafo complementar é um grafo simples cujo conjunto de vértices é V e o conjunto de arestas é dado pelos pares não adjacentes em G
Um grafo é autocomplementar se é isomorfico ao seu complemento
Automorfismo de um grafo é um isomorfismo de um grafo consigo mesmo. automorfismo de um grafo reflete as suas simetrias.
se há automorfismo que mapeia v em u, dizemos que v e u são similares
Grafos em que todo par de vértice é similar são chamados de vértice transitivo
kn, kn,n e cn são vértice- transitivos.
equivalente para aresta-transitivo
grafo rotulado: um grafo onde os vértices são rotulados, mas arestas não.
dado n possuem 2 n(n-1)/2 possíveis grafos simples rotulados de n vértices 
subgrafos: remoção de arestas ou vértices