Modelos Gráficos
A parte anterior trouxe as diferentes ferramentas de raciocínio, revisão e solução de problemas. Nesta parte, estudaremos as estruturas discretas que formam a base da formulação de muitos problemas da vida real.
As duas estruturas discretas que iremos cobrir são gráficos e árvores. Um gráfico é um conjunto de pontos, chamados de nós ou vértices, que são interconectados por um conjunto de linhas chamadas de arestas. O estudo de gráficos, ougraph theory é uma parte importante de uma série de disciplinas nas áreas de matemática, engenharia e ciência da computação.
O que é um gráfico?
Definition - Um gráfico (denotado como $ G = (V, E) $) consiste em um conjunto não vazio de vértices ou nós V e um conjunto de arestas E.
Example - Vamos considerar que um gráfico é $ G = (V, E) $ onde $ V = \ lbrace a, b, c, d \ rbrace $ e $ E = \ lbrace \ lbrace a, b \ rbrace, \ lbrace a , c \ rbrace, \ lbrace b, c \ rbrace, \ lbrace c, d \ rbrace \ rbrace $
Degree of a Vertex - O grau de um vértice V de um grafo G (denotado por deg (V)) é o número de arestas incidentes com o vértice V.
| Vértice | Grau | Par ou ímpar |
|---|---|---|
| uma | 2 | até |
| b | 2 | até |
| c | 3 | ímpar |
| d | 1 | ímpar |
Even and Odd Vertex - Se o grau de um vértice é par, o vértice é chamado de vértice par e se o grau de um vértice é ímpar, o vértice é chamado de vértice ímpar.
Degree of a Graph- O grau de um gráfico é o maior grau de vértice desse gráfico. Para o gráfico acima, o grau do gráfico é 3.
The Handshaking Lemma - Em um gráfico, a soma de todos os graus de todos os vértices é igual a duas vezes o número de arestas.
Tipos de gráficos
Existem diferentes tipos de gráficos, que aprenderemos na seção seguinte.
Gráfico Nulo
Um gráfico nulo não possui arestas. O gráfico nulo de $ n $ vértices é denotado por $ N_n $
Gráfico Simples
Um gráfico é chamado de gráfico simples / gráfico estrito se o gráfico não for direcionado e não contiver nenhum loop ou arestas múltiplas.
Multi-gráfico
Se em um gráfico várias arestas entre o mesmo conjunto de vértices forem permitidas, ele é chamado de Multigraph. Em outras palavras, é um gráfico com pelo menos um loop ou arestas múltiplas.
Gráfico direcionado e não direcionado
Um gráfico $ G = (V, E) $ é chamado de gráfico direcionado se o conjunto de arestas for feito de um par de vértices ordenado e um gráfico é chamado de não direcionado se o conjunto de arestas for feito de um par de vértices não ordenado.
Gráfico conectado e desconectado
Um gráfico é conectado se quaisquer dois vértices do gráfico estiverem conectados por um caminho; enquanto um gráfico é desconectado se pelo menos dois vértices do gráfico não estiverem conectados por um caminho. Se um gráfico G é desconectado, então cada subgráfico conectado máximo de $ G $ é chamado de um componente conectado do gráfico $ G $.
Gráfico Regular
Um gráfico é regular se todos os vértices do gráfico tiverem o mesmo grau. Em um grafo regular G de grau $ r $, o grau de cada vértice de $ G $ é r.
Gráfico Completo
Um gráfico é chamado de gráfico completo se cada par de dois vértices são unidos por exatamente uma aresta. O gráfico completo com n vértices é denotado por $ K_n $
Gráfico de Ciclo
Se um gráfico consiste em um único ciclo, é denominado gráfico de ciclo. O gráfico do ciclo com n vértices é denotado por $ C_n $
Gráfico Bipartido
Se o conjunto de vértices de um grafo G pode ser dividido em dois conjuntos disjuntos, $ V_1 $ e $ V_2 $, de tal forma que cada aresta do grafo une um vértice em $ V_1 $ a um vértice em $ V_2 $, e não há arestas em G que conectem dois vértices em $ V_1 $ ou dois vértices em $ V_2 $, então o grafo $ G $ é chamado de grafo bipartido.
Gráfico Bipartido Completo
Um grafo bipartido completo é um grafo bipartido no qual cada vértice do primeiro conjunto é unido a cada vértice do segundo conjunto. O gráfico bipartido completo é denotado por $ K_ {x, y} $ onde o gráfico $ G $ contém $ x $ vértices no primeiro conjunto e $ y $ vértices no segundo conjunto.
Representação de Gráficos
Existem basicamente duas maneiras de representar um gráfico -
- Matriz de adjacência
- Lista de Adjacência
Matriz de adjacência
Uma Matriz de Adjacência $ A [V] [V] $ é um array 2D de tamanho $ V \ times V $ onde $ V $ é o número de vértices em um gráfico não direcionado. Se houver uma borda entre $ V_x $ a $ V_y $ então o valor de $ A [V_x] [V_y] = 1 $ e $ A [V_y] [V_x] = 1 $, caso contrário, o valor será zero. E para um gráfico direcionado, se houver uma borda entre $ V_x $ a $ V_y $, então o valor de $ A [V_x] [V_y] = 1 $, caso contrário, o valor será zero.
Adjacency Matrix of an Undirected Graph
Vamos considerar o seguinte grafo não direcionado e construir a matriz de adjacência -
A matriz de adjacência do gráfico não direcionado acima será -
a |
b |
c |
d |
|
a |
0 |
1 |
1 |
0 |
b |
1 |
0 |
1 |
0 |
c |
1 |
1 |
0 |
1 |
d |
0 |
0 |
1 |
0 |
Adjacency Matrix of a Directed Graph
Vamos considerar o seguinte grafo direcionado e construir sua matriz de adjacência -
A matriz de adjacência do gráfico direcionado acima será -
a |
b |
c |
d |
|
a |
0 |
1 |
1 |
0 |
b |
0 |
0 |
1 |
0 |
c |
0 |
0 |
0 |
1 |
d |
0 |
0 |
0 |
0 |
Lista de Adjacência
Na lista de adjacência, um array $ (A [V]) $ de listas encadeadas é usado para representar o grafo G com $ V $ número de vértices. Uma entrada $ A [V_x] $ representa a lista encadeada de vértices adjacentes ao vértice $ Vx-th $. A lista de adjacências do grafo não direcionado é mostrada na figura abaixo -
Gráfico plano vs. não plano
Planar graph- Um gráfico $ G $ é chamado de gráfico planar se puder ser desenhado em um plano sem nenhuma aresta cruzada. Se desenharmos um gráfico no plano sem cruzamento de arestas, isso é chamado de embutir o gráfico no plano.
Non-planar graph - Um gráfico não é plano se não puder ser desenhado em um plano sem o cruzamento das bordas do gráfico.
Isomorfismo
Se dois gráficos G e H contêm o mesmo número de vértices conectados da mesma maneira, eles são chamados de gráficos isomórficos (denotados por $ G \ cong H $).
É mais fácil verificar o não isomorfismo do que o isomorfismo. Se qualquer uma das seguintes condições ocorrer, então dois gráficos não são isomórficos -
- O número de componentes conectados é diferente
- Cardinalidades definidas por vértices são diferentes
- Cardinalidades definidas pela borda são diferentes
- As sequências de graus são diferentes
Exemplo
Os gráficos a seguir são isomórficos -
Homomorfismo
Um homomorfismo de um gráfico $ G $ para um gráfico $ H $ é um mapeamento (pode não ser um mapeamento bijetivo) $ h: G \ rightarrow H $ tal que - $ (x, y) \ in E (G) \ rightarrow (h (x), h (y)) \ em E (H) $. Ele mapeia vértices adjacentes do gráfico $ G $ aos vértices adjacentes do gráfico $ H $.
Propriedades dos homomorfismos
Um homomorfismo é um isomorfismo se for um mapeamento bijetivo.
O homomorfismo sempre preserva as arestas e a conexão de um gráfico.
As composições de homomorfismos também são homomorfismos.
Saber se existe algum grafo homomórfico de outro grafo é um problema NPcompleto.
Gráficos de Euler
Um gráfico conectado $ G $ é chamado de gráfico de Euler, se houver uma trilha fechada que inclui todas as arestas do gráfico $ G $. Um caminho de Euler é um caminho que usa cada aresta de um gráfico exatamente uma vez. Um caminho de Euler começa e termina em vértices diferentes.
Um circuito de Euler é um circuito que usa cada aresta de um gráfico exatamente uma vez. Um circuito de Euler sempre começa e termina no mesmo vértice. Um grafo conectado $ G $ é um grafo de Euler se e somente se todos os vértices de $ G $ forem de grau par, e um grafo conectado $ G $ é euleriano se e somente se seu conjunto de arestas puder ser decomposto em ciclos.
O gráfico acima é um gráfico de Euler como $ “a \: 1 \: b \: 2 \: c \: 3 \: d \: 4 \: e \: 5 \: c \: 6 \: f \: 7 \: g ”$ cobre todas as arestas do gráfico.
Gráficos Hamiltonianos
Um grafo conectado $ G $ é chamado de grafo hamiltoniano se houver um ciclo que inclui todos os vértices de $ G $ e o ciclo é chamado de ciclo hamiltoniano. O passeio hamiltoniano no gráfico $ G $ é um passeio que passa por cada vértice exatamente uma vez.
Se $ G $ é um gráfico simples com n vértices, onde $ n \ geq 3 $ Se $ deg (v) \ geq \ frac {n} {2} $ para cada vértice $ v $, então o gráfico $ G $ é Gráfico hamiltoniano. Isso é chamadoDirac's Theorem.
Se $ G $ é um gráfico simples com $ n $ vértices, onde $ n \ geq 2 $ if $ deg (x) + deg (y) \ geq n $ para cada par de vértices não adjacentes x e y, então o o gráfico $ G $ é o gráfico hamiltoniano. Isso é chamadoOre's theorem.
