CICLO:
TERCERO
¿QUÉ ES UN GRAFO?
Un grafo es la representación simbólica de los elementos constituidos de un sistema o
conjunto, mediante esquemas gráficos. se puede decir también, que un grafo consiste en un
conjunto de nodos (también llamados vértices) y un conjunto de arcos (aristas) que
establecen relaciones entre nodos.
Es importante resaltar, que informalmente un grafo se define como G = (V, E), siendo los
elementos de V los vértices o nodos, y los elementos de E, las aristas. formalmente, un
grafo G, se define como un par ordenado, G = (V, E), donde V es un conjunto finito y E es
un conjunto que consta de dos elementos de V.
Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre
unidades que interactúan unas con otras. Por ejemplo, una red de computadoras puede
representarse y estudiarse mediante un grafo, en el cual los vértices representan los
terminales y las aristas representan las conexiones inalámbricas). En fin, prácticamente
cualquier problema puede representarse mediante un grafo.
Partes de un Grafo
Aristas: Son las líneas con las que se unen las aristas de un grafo y con la que se construyen
también caminos. Si la arista carece de dirección se denota indistintamente {a, b} o {b, a},
siendo a y b los vértices que une.
Si {a, b} es una arista, a los vértices a y b se les llama sus extremos.
Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen en el mismo
vértice.
Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son el
mismo.
Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo.
Cruce: Son dos aristas que cruzan en un punto.
Vértices: Son los puntos o nodos con los que está conformado un grafo. Llamaremos grado
de un vértice al número de aristas de las que es extremo. Se dice que un vértice es `par' o
`impar' según lo sea su grado.
Vértices Adyacentes: si tenemos un par de vértices de un grafo (U, V) y si tenemos una
arista que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice
inicial y V el vértice adyacente.
Vértice Aislado: Es un vértice de grado cero.
Vértice Terminal: Es un vértice de grado 1.
Caminos: Se llama camino a una secuencia de vértices de un grafo tal que exista una arista,
cada vértice y el siguiente. Se dice que dos vértices están conectados si existe un camino
que vaya de uno a otro, de lo contrario estarán desconectados.
Los Vértices, son los objetos representados por un punto dentro del
grafo.
Las Aristas, son las líneas que unen dos vértices.
Las Arista Adyacentes, se dice que dos aristas son adyacentes si convergen sobre el
mismo vértice.
Las Aristas Múltiples o Paralelas, dos aristas son múltiples o paralelas si tienen los mismos
vértices en común o incidente sobre los mismos vértices.
Lazo, es una arista cuyos extremos inciden sobre el mismo vértice.
GRAFO DIRIGIDO.
Un grafo dirigido o dígrafo es un tipo de grafo en el cual
las aristas tienen una dirección definida, a diferencia del grafo
generalizado, en el cual la dirección puede estar especificada o
no.
Al igual que en el grafo generalizado, el grafo dirigido está definido por un par de
conjuntos , donde:
, un conjunto no vacío de objetos simples llamados vértices o nodos.
es un conjunto de pares ordenados de elementos
de denominados aristas o arcos, donde por definición un arco va del primer nodo (a) al
segundo nodo (b) dentro del par.
Por definición, los grafos dirigidos no contienen bucles (lazos).
DÍGRAFOS (GRAFOS DIRIGIDOS).
Cada arista del grafo dirigido incluye una flecha para indicar la dirección. La punta de cada
flecha representa el segundo nodo del par ordenado de nodos que constituye un arco y la
cola de la flecha representa el primer nodo del par.
GRAFOS NO DIRIGIDOS.
Un grafo no dirigido o grafo propiamente dicho es un
grafo donde:
es un conjunto de pares no ordenados de elementos de
.
Un par no ordenado es un conjunto de la forma , de manera que .
Para los grafos, estos conjuntos pertenecen al conjunto de potencia de , denotado ,
y son de cardinalidad 2.
GRAFOS MIXTOS
Un grafo mixto es aquel que se define con la capacidad de poder
contener aristas dirigidas y no dirigidas. Tanto los grafos
dirigidos como los no dirigidos son casos particulares de este.
MULTIGRAFO O PSEUDOGRAFO.
Un multigrafo o pseudografo es un grafo que está facultado para tener aristas múltiples; es
decir, aristas que relacionan los mismos nodos. De esta forma, dos nodos pueden estar
conectados por más de una arista. Formalmente, un multigrafo G es un par G:=(V, E)
donde:
V es un conjunto de vértices o nodos
E es un multiconjunto de pares no ordenados de nodos,
llamados aristas o líneas.
V es un conjunto de vértices o nodos
A es un multiconjunto de pares ordenados de nodos,
llamados aristas dirigidas, arcos o flechas.
Ejemplo: Los multigrafos podrían usarse, para modelar las posibles conexiones de vuelo
ofrecidas por una aerolínea. Para este caso tendríamos un grafo dirigido, donde cada nodo
es una localidad y donde pares de aristas paralelas conectan estas localidades, según un
vuelo es hacia o desde una localidad a la otra.
Multidigrafo
Es un grafo dirigido que está facultado para tener aristas múltiples, es decir, aristas con los
mismos nodos iniciales y finales. Formalmente, un multidigrafo G es un par G:=(V,A)
donde:
V es un conjunto de vértices o nodos
A es un multiconjunto de pares ordenados de nodos, llamados aristas
dirigidas, arcos o flechas.
Multidigrafo Mixto
G:=(V,E,A) puede definirse de la misma manera que un grafo mixto, es decir, con la
capacidad de poseer al mismo tiempo aristas dirigidas (A) y no dirigidas (E).
PROPIEDADES DE LOS GRAFOS.
Adyacencia: Dos aristas son adyacentes si tienen un vértice en común, y dos vértices
son adyacentes si una arista los une.
Incidencia: Una arista es incidente a un vértice si ésta lo une a otro.
Ponderación: Corresponde a una función que a cada arista le asocia un valor, para
aumentar la expresividad del modelo.
Etiquetado: Distinción que se hace a los vértices y/o aristas mediante una marca que los
hace unívocamente distinguibles del resto.
GRAFOS PARTICULARES
Grafo Nulo
En este grafo los vértices que lo componen so estás
conectados, esto es, que son vértices aislados, se
puede decir también, que es un grafo trivial que no
tiene vértices ni aristas.
Grafo Vacío:
Es aquel grafo que no tienen aristas.
Grafo Trivial
Es un grafo trivial es un grafo con 0 aristas, y 0 ó 1 vértices. Los
grafos triviales son grafos completos: a aquel que no posee
vértices se le llama grafo nulo, mientras que al que posee un
vértice, se le conoce como grafo singleton.
Grafo Simple
Es aquel grafo que no posee bucles o lazos. Se puede decir
también, que un grafo es simple si a lo más existe una arista
uniendo dos vértices cualesquiera. Esto es equivalente a decir
que una arista cualquiera es la única que une dos vértices
específicos. Un grafo que no es simple se
denomina multigrafo.
Grafo Completo
Un grafo completo es un grafo simple en el que cada par de vértices
están unidos por una arista, es decir, contiene todas las posibles aristas.
Se puede hacer referencia que un grafo completo de n vértices
tiene aristas, y se nota . Es un grafo regular con todos sus vértices
de grado . La única forma de hacer que un grafo completo se torne disconexo a
través de la eliminación de vértices, sería eliminándolos todos.
