Conceitos Flashcards
O que são Grafos?
Um grafo é uma tripla ordenada, formada por um conjunto não vazio de vértices e arestas, e uma função incidência que associa a cada aresta um par não ordenado de vértices, que podem ser não distintos.
Isomorfismo
Dois grafos G e H são considerados Isomórficos, se seus vértices são correspondentes preservando as adjacências.
Grafo vazio
Um grafo com nenhum vértice é chamado de vazio.
Grafo simples
Um grafo é dito simples se não tiver laços nem arestaas paralelas.
Grafo não direcionado
Se o vértice v está ligado a u, então u está ligado a v.
Grafos direcionados (digrafo ou dirigido)
Tem arestas dirigidas, no qual cada aresta é direcionada a um vértice chamado nó terminal.
Grafo completo
um grafo simples de n vértices, em que todo vértice é adjacente a todos os outros vértices.
Grafo bipartido
Um grafo cujo conjunto de vétices pode ser particionado em dois subconjuntos X e Y, de modo que cada aresta tenha uma extremidade em X e uma em Y.
Grafo valorado
é um grafo em que cada aresta tem um valor associado.
Grau do vértice
O grau de um vértice é igual ao número de arestas incidentes a ele, um laço é contado duas vezes.
Grau do vétice em um grafo direcionado
Em um grafo direcionado, grau de um vértice é a soma do número de arestas que saem dele e do número de arestas que chegam nele.
Teorema do aperto de mão (handshaking)
A soma dos graus de todos os vétices de um grafo não direcionado é duas vezes o número de arestas do grafo.
Grafo regular
Um grafo regular quando todos os seus vértices têm o mesmo grau.
