Grafo dirigido
Un grafo dirigido o digrafo es un tipo de grafo en el cual las aristas tienen un
sentido definido,[1] a diferencia del grafo no dirigido, en el cual las aristas
son relaciones simétricas y no apuntan en ningún sentido.
A veces un digrafo es denominado digrafo simple para distinguirlo del caso general
del multigrafo dirigido, donde los arcos constituyen un multiconjunto, en lugar de un
conjunto. En este caso, puede haber más de un arco que una dos vértices en la misma
dirección, distinguiéndose entre sí por su identidad, por su tipo (por ejemplo un tipo de
arco representa relaciones de amistad mientras que el otro tipo representa mensajes
enviados recientemente entre los nodos), o por un atributo como por ejemplo su
importancia o peso. A menudo también se considera que en un digrafo simple no están
permitidos los bucles.
Definición formal
Propiedades
Sea n = |v|el número de nodos de un grafo dirigido, este podrá a lo más tener n² aristas,
y n(n-1) en caso de que se excluyan los bucles.
Grafo no dirigido
Un grafo no dirigido es un tipo de grafo en el cual las aristas representan relaciones
simétricas y no tienen un sentido definido, a diferencia del grafo dirigido, en el cual las
aristas tienen un sentido y por tanto no son necesariamente simétricas.
Grafo no dirigido con dos nodos y una arista.
Vértice (teoría de grafos)
unidad fundamental de la que están formados los grafos
En teoría de grafos, un vértice o nodo es la unidad fundamental de la que están formados
los grafos. Un grafo no dirigido está formado por un conjunto de vértices y un conjunto
de aristas (pares no ordenados de vértices), mientras que un grafo dirigido está compuesto
por un conjunto de vértices y un conjunto de arcos (pares ordenados de vértices). En este
contexto, los vértices son tratados como objetos indivisibles y sin propiedades, aunque
puedan tener una estructura adicional dependiendo de la aplicación por la cual se usa el
grafo; por ejemplo, una red semántica es un grafo en donde los vértices representan
conceptos o clases de objetos.
Un grafo con 6 vértices y 7 aristas.
Los dos vértices que conforman una arista se llaman puntos finales ("endpoints", en
inglés), y esa arista se dice que es incidente a los vértices. Un vértice w es adyacente a
otro vértice v si el grafo contiene una arista (v,w) que los une. La vecindad de un
vértice v es un grafo inducido del grafo, formado por todos los vértices adyacentes a v.
Vértices y grados
El grado de un vértice en un grafo es el número de aristas incidentes a él. Un vértice
aislado es un vértice con grado cero; esto es, un vértice que no es punto final de ninguna
arista. Un vértice hoja es un vértice con grado uno. En un grafo dirigido, se puede
distinguir entre grado de salida ("outdegree", número de aristas que salen del vértice) y
grado de entrada ("indegree", número de aristas que llegan al vértice); un vértice
fuente es un vértice con grado de entrada cero, mientras que un sumidero es un vértice
con grado de salida cero.
Arista
Una arista o arco es una relación matemática que conecta dos vértices. Una arista
dirigida es una arista de un digrafo y tiene una dirección asociada consigo, esto es, posee
un vértice inicial y un vértice final. Una arista no dirigida es una donde no se distingue un
vértice inicial ni uno final.
Arista (teoría de grafos)
En teoría de grafos, una arista o línea[1] corresponde a una relación entre
dos vértices de un grafo. En un grafo no dirigido, se trata de relaciones simétricas sin
dirección, mientras que en un grafo dirigido son relaciones direccionales, también
conocidas como arcos.[2]
Para caracterizar un grafo G son suficientes únicamente el conjunto de todas sus
aristas, comúnmente denotado con la letra E (del término en inglés edge), junto con
el conjunto de sus vértices, denotado por V. Así, dicho grafo se puede representar
como G(V,E), o bien G = (V,E).
En un grafo, dos vértices son adyacentes si están conectados por una arista. En tal
caso, cada uno de estos vértices es incidente a dicha arista.[2]
Representaciones gráficas de un grafo no dirigido, de un grafo dirigido, y de un grafo dirigido
etiquetado.
Aristas múltiples
En teoría de grafos, las aristas múltiples (también llamadas aristas paralelas o una multi-
arista), son dos o más aristas que son incidentes (es decir, que conectan) a al menos
dos vértices. Los grafos sin aristas múltiples son llamados grafos simples.
Cuando un grafo admite aristas múltiples, se llama multigrafo.
Dependiendo del contexto, un grafo puede definirse de manera que permita o no
la presencia de aristas múltiples (del mismo modo que a veces se permite y a veces
no la presencia de bucles):
En un contexto en que se permiten la presencia de aristas múltiples y bucles, un grafo sin
bucles es usualmente llamado multigrafo.[1]
En un contexto en que no se permiten aristas múltiples y bucles, un multigrafo o
pseudografo es definido para referirse a un "grafo" que puede tener bucles y aristas
múltiples.[2]
Las aristas múltiples son útiles, por ejemplo, en la consideración de redes eléctricas,
desde un punto de vista de teoría de grafos.[3]
Un grafo planar permanece planar si es añadida una arista entre dos vértices ya
unidos por una arista; por lo tanto, la agregación de aristas múltiples preserva la
planaridad.[4]
Subgrafo
Un subgrafo de un grafo G es un grafo cuyo conjunto de vértices es un subconjunto del
de G, cuyo conjunto de aristas es un subconjunto del conjunto de las aristas de G, y tal que
la aplicación w es la restricción de la aplicación de G.
Un subgrafo de un grafo G es un grafo cuyos conjuntos de vértices y aristas son
subconjuntos de los de G. Se dice
que un grafo G contiene a otro grafo H si algún subgrafo de G es H o es isomorfo a H
(dependiendo de las
necesidades de la situación).
El subgrafo inducido de G es un subgrafo G' de G tal que contiene todas las aristas
adyacentes al subconjunto de
vértices de G.
Definición:
Sea G=(V, A). G’=(V’,A’) se dice subgrafo de G si:
1- V’ V
2- A' A
3- (V’,A’) es un grafo
• Si G’=(V’,A’) es subgrafo de G, para todo v G se cumple gr (G’,v)≤ gr (G, v)
Camino (teoría de grafos)
secuencia de vértices dentro de un grafo tal que exista una arista entre cada vértice y el siguiente
En teoría de grafos, un camino (en inglés, walk, y en ocasiones traducido también
como recorrido)[1] es una sucesión de vértices y aristas dentro de un grafo, que
empieza y termina en vértices, tal que cada vértice es incidente con las aristas que
le siguen y le preceden en la secuencia.[2] Dos vértices están conectados o son
accesibles si existe un camino que forma una trayectoria para llegar de uno al otro;
en caso contrario, los vértices están desconectados o bien son inaccesibles. [1]
Dos vértices pueden estar conectados por varios caminos. La longitud de un
camino es su número de aristas. Así, en un grafo no dirigido, los vértices adyacentes
están conectados por un camino de longitud 1, los segundos vecinos por un camino
de longitud 2, y así sucesivamente. Un grafo no dirigido es conexo si todos sus
vértices están conectados a través de un camino. [2] Un grafo conexo cuyos vértices
y aristas permiten definir un camino es un grafo camino.
Definición formal
Grafo ciclo
En teoría de grafos, un grafo ciclo o simplemente ciclo es un grafo que consiste en
un camino simple cerrado, es decir, en el que no se repite ningún vértice, salvo el primero
con el último. Un grafo ciclo de n vértices se denota Cn El número de vértices en un grafo
ciclo es igual al número de aristas. En su versión más común, como grafo no dirigido, cada
vértice tiene grado 2, por lo que es un grafo 2-regular; en su versión dirigida, en cambio,
se trata de un grafo 1-regular.
Definición formal
Propiedades
Grafo conexo
En teoría de grafos, un grafo conexo o conectado[1] es un grafo en que todos
sus vértices están conectados por un camino (si el grafo es no dirigido)[2] o por
un semicamino (si el grafo es dirigido). Un grafo que no es conexo se denomina grafo
disconexo o inconexo. Los subgrafos conexos máximos de un grafo no dirigido se
llaman componentes o componentes conexos.[1] Para el caso de los grafos dirigidos, si no
se considera el sentido de las aristas, se habla de componente débilmente conexo,
mientras que sí se considera el sentido, se habla de componente fuertemente conexo.
Grafo conexo. Grafo disconexo con tres componentes.
Un grafo es doblemente conexo si cada par de vértices está conectado por al menos
dos caminos disjuntos; es decir, es conexo y no tiene vértices de corte, esto es,
vértices tales que al quitarlos el grafo resultante se vuelve disconexo.
En ciencias de la computación, es posible determinar si un grafo es conexo usando
un algoritmo de búsqueda en anchura (BFS) o búsqueda en profundidad (DFS). En
términos matemáticos, la propiedad de un grafo de ser (fuertemente) conexo
permite establecer con base en él una relación de equivalencia para sus vértices, la
cual lleva a una partición de estos en componentes (fuertemente) conexas, es decir,
porciones del grafo, que son (fuertemente) conexas cuando se consideran como
grafos aislados. Esta propiedad es importante para muchas demostraciones en
teoría de grafos.
Conectividad en grafos dirigidos
En un grafo dirigido, se distingue entre los siguientes tipos de conectividad:[1]
grafo débilmente conexo: todos los pares de vértices están débilmente conectados, es
decir, unidos por un «semicamino» (camino que no considera la dirección de las aristas);
grafo unilateralmente conexo: todos los pares de vértices están unilateralmente
conectados, es decir, unidos por un camino que va desde uno hasta el otro;
grafo fuertemente conexo: todos los pares de vértices están fuertemente conectados, es
decir, unidos por al menos dos caminos, uno que va desde uno hasta el otro, y viceversa;
grafo recursivamente conexo: todos los pares de vértices están recursivamente
conectados, es decir, están fuertemente conectados y el camino desde uno hasta el otro usa
los mismos vértices y aristas que los del camino inverso.
Si se cumple alguno de estos tipos de conexiones, entonces se cumplen todos los
tipos anteriores.[1
