Grafos

wow

Grafos

¡Vamos!

En matemáticas y ciencias de la computación, un grafo (del griego grafos: dibujo, imagen)1​ es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto.2​Son objeto de estudio de la teoría de grafos.3​ Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas o arcos).

Grafo no dirigido Un grafo no dirigido o grafo propiamente dicho es un grafo es un conjunto de pares no ordenados de elementos de Por definición, los grafos dirigidos no contienen bucles. 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.

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.

Grafo completo

Un grafo completo es un grafo en el que cada par de vértices está unido por una arista. Un grafo completo contiene todas las aristas posibles.

Grafo finito

Un grafo finito es un grafo en el que el conjunto de vértices y el conjunto de aristas son conjuntos finitos. En caso contrario, se denomina grafo infinito. Comúnmente en teoría de grafos se implica que los grafos discutidos son finitos. Si los grafos son infinitos, suele indicarse específicamente.

Grafo conectado

En un grafo dirigido, un par ordenado de vértices (x, y) se llama fuertemente conectado si un camino dirigido lleva de x a y. En caso contrario, el par ordenado se denomina débilmente conectado si un camino no dirigido va de x a y después de reemplazar todas sus aristas dirigidas por aristas no dirigidas. En caso contrario, el par ordenado se denomina desconectado. Un grafo fuertemente conectado es un grafo dirigido en el que cada par ordenado de vértices del grafo está fuertemente conectado. En caso contrario, se denomina grafo débilmente conectado si cada par ordenado de vértices del grafo está débilmente conectado. En caso contrario, se denomina grafo desconectado.

Grafo Biparito

Un grafo bipartito' es un grafo simple en el que el conjunto de vértices puede ser particionado en dos conjuntos, W y X, de modo que no hay dos vértices en W que compartan una arista común y no hay dos vértices en X que compartan una arista común. Alternativamente, es un grafo con un número cromático de 2. En un grafo bipartito completo, el conjunto de vértices es la unión de dos conjuntos disjuntos, W y X, de modo que cada vértice en W es adyacente a cada vértice en X pero no hay aristas dentro de W o X.

Grafo de trayectorias

Un grafo de caminos o grafo lineal de orden n ≥ 2 es un grafo en el que los vértices se pueden enumerar en un orden v1, v2, ... , vn tal que las aristas son las {mset}} donde i = 1, 2, ..., n - 1. Los grafos de sendero se pueden caracterizar como grafos conexos en los que el grado de todos los vértices menos dos es 2 y el grado de los dos vértices restantes es 1. Si un grafo de sendero aparece como un subgrafo de otro grafo, es un camino en ese grafo.

Grafo ciclico

Un grafo de ciclo o grafo circular de orden n ≥ 3 es un grafo en el que los vértices se pueden enumerar en un orden v1, v2, ... , vn tal que las aristas son las {vi, vi+1} donde i = 1, 2, ... , n - 1, más la arista {vn, v1}. Los grafos de ciclo pueden caracterizarse como grafos conexos en los que el grado de todos los vértices es 2. Si un grafo de ciclo aparece como subgrafo de otro grafo, es un ciclo o circuito en ese grafo.

Grafo de arbol

Un árbol es un grafo no dirigido en el que dos vértices cualesquiera están conectados por exactamente una trayectoria, o equivalentemente un conectado no dirigido cíclico. Un bosque es un grafo no dirigido en el que dos vértices cualesquiera están conectados por a lo sumo un camino, o equivalentemente un grafo acíclico no dirigido, o equivalentemente una unión disjunta de árboles.

Grafo Poliarbol

Un poliárbol (o árbol dirigido o árbol orientado o red uniconexa) es un grafo acíclico dirigido (DAG) cuyo grafo no dirigido subyacente es un árbol. Un polibosque (o bosque dirigido o bosque orientado) es un grafo acíclico dirigido cuyo grafo no dirigido subyacente es un bosque. Clases avanzadas

Otros tipos de grafos

Grafo nulo: aquel que no tiene vértices ni aristas. Nótese que algunas personas exigen que el conjunto de vértices no sea vacío en la definición de grafo. Grafo vacío: aquel que no tiene aristas. Grafo trivial: aquel que tiene un vértice y ninguna arista. Grafo simple: aquel que no posee bucles ni aristas paralelas. Consultar variantes en esta definición. Multigrafo (o pseudografo): G es multigrafo si y solo si no es simple. Grafo completo: grafo simple en el que cada par de vértices están unidos por una arista, es decir, contiene todas las posibles aristas.