5 1 1 Tipos de Grafos - Lupiwi Chan

Vista previa del material en texto

Matemáticas discretas
Tipos de grafos
 grafo dirigido y no dirigido
1
Gráfico dirigido
Un grafo dirigido es aquel en el que los arcos tienen un único sentido. 
En este caso, un arco se dirige desde el nodo origen hasta el nodo 
destino. Se dice que el nodo origen precede al nodo destino, y que 
éste sucede al origen. Los arcos de un grafo dirigido se representan 
gráficamente con flechas.
3
Un grafo dirigido es 
aquel en el que todas sus 
aristas tienen sentido o 
dirección.
Un grafo dirigido lo constituye la red de aguas de una ciudad ya que 
cada tubería sólo admite que el agua la recorra en un único sentido
4
Ejemplo
Los grafos no dirigidos son aquellos que constan un conjunto de vértices 
que están conectados a un conjunto de aristas de forma no direccional.
Esto significa que una arista puede indistintamente recorrerse desde 
cualquiera de sus puntos y en cualquier dirección.
Gráfico no dirigido 
5
Un grafico no dirigido es la red de carreteras de un país representa en 
general un grafo no dirigido, puesto que una misma carretera puede ser 
recorrida en ambos sentidos
6
Ejemplo
 multigrafo y grafo bipartido
2
multigrafo
Un multigrafo o grafo multivariado es una generalización de un grafo que 
permite aristas múltiples, o equivalentemente, más de un conjunto de aristas. 
De esta forma, dos nodos pueden estar conectados por más de una arista. 
Algunos autores permiten que los multigrafos tengan bucles, es decir, que una 
arista conecte a un nodo consigo mismo. Un pseudografo se puede definir 
como un sinónimo de multigrafo, aunque en ocasiones también se utiliza para 
distinguir a los multigrafos en general, de aquellos que permiten bucles. Si se 
consideran aristas dirigidas, al multigrafo también se le conoce como multigrafo 
dirigido o multidigrafo. También se puede hablar de grafo complejo en oposición 
a un grafo simple (esto es, un grafo sin bucles ni aristas múltiples), como un 
grafo que posee bucles y/o al menos un par de vértices con más de una arista.
8
Formalmente, un multigrafo G es un par ordenado G = (V, E) donde
• V es un conjunto de vertice o nodos
• E es un multiconjuto (finito) de aristas o líneas, o alternativamente, 
una familia de conjuntos de aristas.
9
Grafo bipartito
En teoría de grafos, un grafo bipartito es un grafo cuyos vértices se 
pueden separar en dos conjuntos disjuntos, de manera que 
las aristas no pueden relacionar vértices de un mismo conjunto. 
Un grafo bipartito completo es un grafo bipartito en que todos los 
vértices de uno de los subconjuntos están relacionados con los del otro 
subconjunto. 
Este concepto se puede generalizar al de grafo s-partito, como un grafo 
cuyo conjunto de vértices se puede particionar en s subconjuntos, de 
modo que las aristas solo conectan a vértices de subconjuntos 
diferentes. Análogamente, también se puede definir un grafo s-bipartito 
completo, como uno en que todos los pares de vértices pertenecientes 
a subconjuntos diferentes son adyacentes.
10
✗ Un grafo G= (N, E) es bipartito si N se pueden separar en dos conjuntos U y V tal que 
se cumple
• U u V = N
• U Ω V = 0
11
 grafo simple y Regular
3
grafo simple 
Es un tipo de grafo el cual no incluye ciclos o bucles ni aristas paralelas 
o múltiples.
13
grafo Regular
Es un grafo donde todos sus vértices tiene el mismo grado 
14
grafo nulo y pseudografo
4
grafo nulo
16
En teoría de grafos, el grafo nulo es un grafo trivial que no tiene vértices 
ni aristas. En teoría de categorías, el grafo nulo es el objeto inicial de la 
categoría de los grafos. Ya que no posee vértices entonces tampoco 
tiene componentes conexos.
pseudografo
 Un pseudografo se puede definir como un sinónimo de 
multigrafo, aunque en ocasiones también se utiliza para 
distinguir a los multigrafos en general, de aquellos que 
permiten bucles.
17