Flashcards
Grafos- noções básicas
Flashcards do conjunto (19)
- 1Grafo orientadoAs arestas são arcos A.______>.B
Têm uma direção - 2MultigrafoÉ um grafo que tem arestas paralelas e/ou lacetes.
- 3Gráfico simplesNão tem arestas paralelas nem lacetes
- 4Vértices adjacentesDizem-se adjacentes quando estão ligados por uma aresta:
A.______B - 5Aresta incidenteAresta dos vértices adjacentes
A_______B - 6Aresta adjacenteArestas que têm um vértice em comum
A____B____C
AB e BC são adjacentes - 7CaminhoComeça num vértice e acaba no outro
- 8Comprimento de A____B___C2
- 9CircuitoComeça e acaba no mesmo vértice
- 10SubgrafoÉ a parte de um grafo
- 11Grafo conexoÉ conexo se existir um caminho a unir quaisquer 2 dos seus vértices
- 12A aresta que torna um grafo conexo chama-seponte
- 13Grau de um vérticeÉ igual ao nº de arestas que começam/terminam naquele vértice
- 14Ordem de um grafoRepresenta o nº de vértices
- 15Grafo regularÉ um grafo que tem todos os vértices com o mesmo grau
- 16Grafo ponderadoArestas têm pesos
- 17Grafo completoHá pelo menos 1 aresta para cada par de vértices
- 18Grafo completo e simplesNão existem arestas paralelas/lacetes.
Cada par de vértices está ligado por uma aresta
- 19Grafos completos e simples têm sempre vértices com grau:n-1