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
No comments