A palavra grafo tem vários significados. Em linguagem não matemática, refere-se a um método de representação de uma ideia ou conceito, por meio de uma ilustração ou por escrito. Tanto em matemática, como na linguagem corrente, costuma referir-se a um diagrama usado para exibir o relacionamento entre duas grandezas.
Matematicamente dizemos que um grafo é um par G equals open parentheses V comma E close parentheses, em que V é um conjunto finito e E é um conjunto de subconjuntos de dois elementos de V. Os elementos de V são chamados vértices do grafo e os elementos de E são as arestas do grafo.
Um famoso desafio (relacionado ao estudo de grafos) que costuma ser apresentado a crianças consiste em desenhar o esquema apresentado na figura a seguir sem tirar a ponta do lápis do papel e sem repetir linhas.
Grafo de casa
Considerando o problema apresentado como um grafo, apresente uma solução para o que é solicitado em cada um dos itens a seguir:
a. Determine o grafo G representado pelo esquema da figura apresentada.
b. Você conseguiria fazer esse desenho, sem levantar o lápis ou repetir linhas, mas começando pelo telhado (vértices 1, 2 ou 3)? Por quê?
Soluções para a tarefa
Resposta:
1 a.
O ponto G pode chamar de grafo conexo, um grafo conexo se existe um caminho, ligando de unidade de qualquer de qualquer nó para qualquer outro. Cada um dos grafos é conexo, outra forma de definir a conexidade é observar que o grafo G é conexo se, e só se, existir um caminho entre quaisquer dois vértices de G. A figura abaixo mostra um grafo ou dois grafos, depende da situação.
Ponto G da tarefa
G = (V, E) "V = Vertices E= Arestas"
V = (1, 2, 3, 4, 5)
E = (1,2),(1,3),(1,4),(1,5),(2,3),(3,5),(3,4),(5,4)
b.
Resposta:
Tem que passar de ponto a ponto e não se pode passar pela mesma linhas duas vezes foi fácil, isso é chamado um grafo completo é definido como um grafo onde todo par de vértices é ligado por uma aresta, um grafo completo com K1 vértices é denotado por K2 exemplo K3.
A figura ilustra os grafos simples completo com 1, 2, 3, 4 e 5 vértices, grafo simples completo com vértices é denotado.
Explicação passo-a-passo:
