6.1.2 Tipos de grafos (Simples, completos, bipartidos, planos, conexos, ponderados)

6.1.2 Tipos de grafos (Simples, completos, bipartidos, planos, conexos, ponderados)

Grafo

Un grafo es un conjunto de vértice o nodos unidos por aristas o arcos.

Grafo acíclico

Es aquel  grafo no contiene ningún ciclo simple.

Grafo cíclico

Un grafo se dice cíclico si contiene algún ciclo simple.

Grafo bipartito

Un grafo bipartito es cualquier grafo, cuyos vértices pueden ser divididos en dos conjuntos, tal que no haya aristas entre los vértices del mismo conjunto. Se ve que un grafo es bipartito si no hay ciclos de longitud impar.

Grafo completo

Un grafo es completo si cada vértice tiene un grado igual a n-1, donde n es el número de vértice que compone el grafo. Además  es un grafo simple en el que cada vértice es adyacente a cualquier todo otro vértice.

Grafo conexo

Decimos que es un grafo conexo, si es posible formar un camino desde cualquier vértice a cualquier otro en el grafo.

Grafo denso

Un grafo denso es aquel grafo en el que el número de aristas está cercano al número de máximo de aristas.

Grafo dirigido

Es un conjunto de vértices V y un conjunto de aristas E tal que para cada arista perteneciente al conjunto de aristas E se asocia con dos vértices en forma ordenada.

Grafo no dirigido

Son aquellos grafos  en los cuales los lados no están orientados (no son flechas). Cada lado se representa entre paréntesis, separando sus vértices por comas

Grafo nulo

El grafo nulo es el grafo cuyos conjuntos de aristas y de vértices son vacíos.

 Grafo plano

Un grafo plano es uno que es posible dibujar en el plano sin que ningún par de aristas se crucen entre sí.

Grafo ponderado

Un grafo ponderado es aquel que  asocia un valor o peso a cada arista en el grafo. El peso de un camino en un grafo con pesos es la suma de los pesos de todas las aristas atravesadas.

Grafo regular

Un grafo regular es un grafo cuyos vértices tienen el mismo grado.

Grafo simple

Un grafo simple es un grafo o dígrafo que no tiene bucles, y que no es un multígrafo.

Grafo no Simple:

Grafo no  dirigido que tiene lados paralelos y lazos.

Grafo trivial

Un grafo trivial es  aquel  grafo vacío con un único vértice.

Grafo vacío

Un grafo vacío es el grafo cuyo conjunto de aristas es vacío.