Ver el código de «Grafo»

{{otros usos}}
{{referencias|t=20150529172849|matemáticas}}
{{otros usos|Teoría de grafos|la teoría en torno a este objeto matemático}}
[[Archivo:6n-graf.svg|miniatura|250px|Grafo etiquetado con 6 vértices y 7 aristas.]]

En [[matemática]]s y [[ciencias de la computación]], un '''grafo''' (del [[Idioma griego|griego]] ''grafos'': dibujo, imagen)<ref> {{ Cita DLE | grafo | fechaacceso = 14 de agosto de 2019 | definición =  Diagrama que representa mediante puntos y líneas las relaciones entre pares de elementos y que se usa para resolver problemas lógicos, topológicos y de cálculo combinatorio. }} </ref> es un conjunto de objetos llamados [[Vértice (teoría de grafos)|vértices]] o [[Vértice (teoría de grafos)|nodos]] unidos por enlaces llamados [[Arista (teoría de grafos)|aristas]] o [[Arista (teoría de grafos)|arcos]], que permiten representar [[Relación binaria|relaciones binarias]] entre elementos de un [[conjunto]].<ref>{{cita libro|apellido=Trudeau|nombre=Richard J.|título=Introduction to Graph Theory (Edición corregida y aumentada.)|url=https://archive.org/details/introductiontogr0000trud|año=1993|editor=Dover Pub.|isbn=978-0-486-67870-2}}</ref>
Son objeto de estudio de la [[teoría de grafos]].<ref name=":0">{{cite book|last=Trudeau|first=Richard J.|title=Introduction to Graph Theory|year=1993|publisher=Dover Pub.|location=New York|isbn=978-0-486-67870-2|pages=19|url=http://store.doverpublications.com/0486678709.html|edition=Corrected, enlarged republication.|access-date=2012-08-08|quote=A graph is an object consisting of two sets called its ''vertex set'' and its ''edge set''.|archive-date=5 May 2019|archive-url=https://web.archive.org/web/20190505192352/http://store.doverpublications.com/0486678709.html|url-status=}}</ref>

Típicamente, un grafo se representa gráficamente como un conjunto de puntos unidos por líneas (aristas o arcos).

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 [[Terminal de computadora|terminales]] y las aristas representan conexiones (las cuales, a su vez, pueden ser [[cable]]s o [[Red inalámbrica|conexiones inalámbricas]]).

Prácticamente cualquier problema puede representarse mediante un grafo, y su estudio trasciende a las diversas áreas de las [[ciencias exactas]] y las [[ciencias sociales]].

Por lo general, un grafo se representa en forma de diagrama como un conjunto de puntos o círculos para los vértices, unidos por líneas o curvas para los bordes. Los grafos son uno de los objetos de estudio de las matemáticas discretas.

Los bordes pueden ser dirigidos o no dirigidos. Por ejemplo, si los vértices representan personas en una fiesta y hay un borde entre dos personas si se dan la mano, entonces este grafo no está dirigido porque cualquier persona A puede darle la mano a una persona B solo si B también le da la mano a A. Por el contrario, si una ventaja de una persona A a una persona B significa que A le debe dinero a B , entonces este grafo es dirigido, porque la deuda no es necesariamente recíproca.

Los grafos son el tema básico estudiado por la teoría de grafos. La palabra «grafo» (en inglés, ''graph'') fue utilizada por primera vez en este sentido por JJ Sylvester en 1878 debido a una relación directa entre las matemáticas y la estructura química (lo que él llamó una imagen químico-gráfica).<ref>See:
* J. J. Sylvester (February 7, 1878) [https://books.google.com/books?id=KcoKAAAAYAAJ&q=Sylvester&pg=PA284 "Chemistry and algebra,"] {{Wayback|url=https://books.google.com/books?id=KcoKAAAAYAAJ&q=Sylvester&pg=PA284|date=20230412144211}} ''Nature'', ''17'' : 284. {{doi|10.1038/017284a0}}. From page 284: "Every invariant and covariant thus becomes expressible by a ''graph'' precisely identical with a Kekuléan diagram or chemicograph."
* J. J. Sylvester (1878) [https://books.google.com/books?id=1q0EAAAAYAAJ&pg=PA64 "On an application of the new atomic theory to the graphical representation of the invariants and covariants of binary quantics, – with three appendices,"] {{Wayback|url=https://books.google.com/books?id=1q0EAAAAYAAJ&pg=PA64|date=20230204142957}} ''American Journal of Mathematics, Pure and Applied'', ''1'' (1) : 64–90. {{doi|10.2307/2369436}}. {{JSTOR|2369436}}. The term "graph" first appears in this paper on page 65.</ref><ref>{{Cite book
 | title = Handbook of graph theory
 | first1 = Jonathan L.
 | last1 = Gross
 | first2 = Jay
 | last2 = Yellen
 | publisher = [[CRC Press]]
 | year = 2004
 | page = [https://books.google.com/books?id=mKkIGIea_BkC&pg=PA35 35]
 | isbn = 978-1-58488-090-5
 | url = https://books.google.com/books?id=mKkIGIea_BkC
 | access-date = 2016-02-16
 | archive-date = 2023-02-04
 | archive-url = https://web.archive.org/web/20230204142959/https://books.google.com/books?id=mKkIGIea_BkC
 | url-status = 
 }}</ref>

La [[teoría de grafos]] nació en 1736 a través de un [[artículo científico]] escrito por el [[matemático]] [[Suiza|suizo]] [[Leonhard Euler]], donde resolvió el [[problema de los puentes de Königsberg]] utilizando los conceptos actualmente conocidos como [[Camino (teoría de grafos)|caminos]] y [[grado (teoría de grafos)|grado]] sobre [[multigrafo]]s.

== Definiciones ==
Un '''grafo''' <math>G</math> es un [[par ordenado]] <math>G=(V,E)</math>, donde:
* <math>V</math> es un [[conjunto]] de [[Vértice (teoría de grafos)|vértices]] o nodos, y
* <math>E</math> es un conjunto de [[Arista (teoría de grafos)|aristas]] o arcos, que [[Relación matemática|relacionan]] estos nodos.

Normalmente <math>V</math> suele ser [[Conjunto finito|finito]]. Muchos resultados importantes sobre grafos no son aplicables para ''grafos infinitos''.

Se llama '''orden''' del grafo <math>G</math> a su número de vértices, <math>|V|</math>.

El [[Grado (teoría de grafos)|grado]] de un vértice o nodo <math>v \in V</math> es igual al número de arcos que lo tienen como extremo.

Un [[Bucle (teoría de grafos)|bucle]] es una arista que relaciona al mismo nodo; es decir, una arista donde el nodo inicial y el nodo final coinciden.

Dos o más aristas son [[Aristas múltiples|paralelas]] si relacionan el mismo par de vértices.

=== Grafo no dirigido ===
{{AP|Grafo no dirigido}}
[[Archivo:Kaari suuntaamaton graafiteoria.png|miniatura|Grafo no dirigido]]

Un '''grafo no dirigido ''' o '''grafo propiamente dicho''' es un grafo <math>G = (V, E)</math> donde:
* <math>V\neq\emptyset</math>
* <math>E\subseteq \{x\in\mathcal P(V): |x|=2\}</math> es un conjunto de ''pares no ordenados'' de elementos de <math>V\,</math>.

Un '''par no ordenado''' es un conjunto de la forma <math>\{a, b\}</math>, de manera que <math>\{a, b\}=\{b, a\}</math>. Para los grafos, estos conjuntos pertenecen al [[conjunto potencia]] de <math>V</math>, denotado <math>\mathcal P(V)</math>, y son de [[cardinalidad]] 2.

=== Grafo dirigido ===
[[Archivo:Kaari suunnattu graafiteoria.png|miniatura|Grafo dirigido]]
{{AP|Grafo dirigido}}
Un '''grafo dirigido''' o '''digrafo''' es un grafo <math> G = (V, E)</math> donde:
* <math>V\neq\emptyset</math>
* <math>E \subseteq \{(a,b) \in V \times V: a \neq b \}\,</math> es un conjunto de [[par ordenado|pares ordenados]] de elementos de <math>V\,</math>.

Dada una arista <math>(a,b)</math>, <math>a</math> es su ''nodo inicial'' y <math>b</math> su ''nodo final''.

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.

=== Variantes sobre las definiciones principales ===
Algunas aplicaciones requieren extensiones más generales a las dos propuestas clásicas de grafos.
Aunque la definición original los permite, según la aplicación concreta pueden ser válidos o no. A veces <math>V</math> o <math>E</math> pueden ser un [[multiconjunto]], pudiendo haber más de una arista entre cada par de vértices. La palabra ''grafo'' (a secas) puede permitir o no múltiples aristas entre cada par de vértices, dependiendo del autor de la referencia consultada. Si se quiere remarcar la inexistencia de múltiples aristas entre cada par de vértices (y en el caso no dirigido, excluir bucles) el grafo puede llamarse '''simple'''. Por otra parte, si se quiere asegurar la posibilidad de permitir múltiples aristas, el grafo puede llamarse '''[[multigrafo]]''' (a veces se utiliza el término '''pseudografo''' para indicar que se permiten tanto bucles como múltiples aristas entre cada par de vértices).

== Propiedades ==

* '''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 (costo, peso, longitud, etc.), para aumentar la expresividad del modelo. Esto se usa mucho para problemas de optimización, como el del [[Problema del viajante|vendedor viajero]] o del [[Algoritmo de Dijkstra|camino más corto]].
* '''Etiquetado:''' distinción que se hace a los vértices y/o aristas mediante una marca que los hace unívocamente distinguibles del resto.

== Representación ==
[[Archivo:Matriz de adyacencia.jpg|miniaturadeimagen|Matriz de adyacencia]]
Las dos representaciones principales de grafos son las siguientes: 
* [[Matriz de adyacencia]] ('''MA'''): Se utiliza una matriz de tamaño ''n'' × ''n'' donde las filas y las columnas hacen referencia a los vértices para almacenar en cada casilla la longitud entre cada par de vértices del grafo. La celda '''MA'''[i, j] almacena la longitud entre el vértice i y el vértice j. Si su valor es infinito significa que no existe arista entre esos vértices, y '''MA'''[i, i] = 0.
[[Archivo:Listas de adyacencia.jpg|miniaturadeimagen|Listas de adyacencia]]
* [[Lista de adyacencia]] ('''LA'''): Se utiliza un vector de tamaño ''n'' (un elemento por cada vértice) donde '''LA'''[i] almacena la referencia a una lista de los vértices adyacentes a i. En una red esta lista almacenará también la longitud de la arista que va desde i al vértice adyacente.

== Ejemplos ==
[[Archivo:6n-graf.svg|250px|derecha]]
La imagen es una representación del siguiente grafo:
* ''V'':={1,2,3,4,5,6}
* ''E'':={{1,2},{1,5},{2,3},{2,5},{3,4},{4,5},{4,6}} 
El hecho que el vértice 1 sea adyacente con el vértice 2 puede ser denotado como 1 ~ 2.

* En la [[teoría de las categorías]] una '''categoría''' puede ser considerada como un '''multigrafo''' dirigido, con los objetos como vértices y los [[morfismo]]s como aristas dirigidas.
* En [[ciencias de la computación]] los grafos dirigidos son usados para representar [[máquinas de estado finito]] y algunas otras estructuras discretas.
* Una [[relación binaria]] ''R'' en un conjunto ''X'' es un grafo dirigido simple. Dos vértices ''a'', ''b'' en ''X'' están conectados por una arista dirigida ''ab'' si ''aRb''.
== Tipos de grafos ==
=== Grafo orientado ===
Una definición de ''grafo orientado'' es que es un grafo dirigido en el que a lo sumo uno de {{nowrap|(''x'', ''y'')}} y {{nowrap|(''y'', ''x'')}} pueden ser aristas del grafo. Es decir, es un grafo dirigido que puede formarse como una [[orientación (teoría de grafos)|orientación]] de un grafo no dirigido (simple). 

Algunos autores utilizan "grafo orientado" con el mismo significado que "grafo dirigido".  Algunos autores usan "grafo orientado" para referirse a cualquier orientación de un grafo no dirigido o multigrafo dado.

=== Grafo regular ===
{{main|Grafo regular}}
Un ''grafo regular'' es un grafo en el que cada vértice tiene el mismo número de vecinos, es decir, cada vértice tiene el mismo grado. Un grafo regular con vértices de grado ''k'' se llama grafo ''k'' -regular o grafo regular de grado ''k''.

=== Grafo completo ===
{{main|Grafo completo}}
[[File:Complete graph K5.svg|thumb|125px|Un grafo completo con cinco vértices y diez aristas. Cada vértice tiene una arista a cada otro vértice.]]

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 [[Conjunto finito| 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 ===
{{main|Conectividad (teoría de grafos)}}
En un grafo no dirigido, un par desordenado de vértices {{nowrap|{{mset|''x'', ''y''}}}} se llama ''conectado'' si un camino lleva de ''x'' a ''y''. En caso contrario, el par desordenado se denomina ''desconectado''.

Un ''grafo conexo'' es un grafo no dirigido en el que cada par desordenado de vértices del grafo está conexo. En caso contrario, se denomina "grafo desconectado".

En un grafo dirigido, un par ordenado de vértices {{nowrap|(''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''.

Un ''[[grafo k-conectado por vértices]]'' o ''[[grafo k-conectado por aristas]]''' es un grafo en el que ningún conjunto de {{nowrap|''k'' - 1}} vértices (respectivamente, aristas) que, cuando se eliminan, desconectan el grafo. Un grafo conectado por vértices ''k'' a menudo se llama simplemente ''grafo conectado por k''.

=== Grafo bipartito ===
{{main|Grafo bipartito}}
Un ''[[grafo bipartito]]'' es un grafo simple en el que el conjunto de vértices puede ser [[Partición de un conjunto|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 ===
{{main|Grafo camino}}
Un ''grafo de caminos'' o ''grafo lineal'' de orden {{nowrap|''n'' ≥ 2}} es un grafo en el que los vértices se pueden enumerar en un orden ''v''<sub>1</sub>, ''v''<sub>2</sub>, ... , ''v''<sub>''n''</sub> tal que las aristas son las {{nowrap|{mset|''v''<sub>''i''</sub>, ''v''<sub>''i''+1</sub>}}}} 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 [[Glosario de teoría de grafos#Subgrafos|subgraph]] de otro grafo, es un [[Camino (teoría de grafos)| camino]] en ese grafo.

=== Grafo plano ===
{{main|Grafo plano}}
Un ''grafo plano'' es un grafo cuyos vértices y aristas se pueden dibujar en un plano de forma que ninguna de las aristas se cruce con otra.

=== Grafo cíclico ===
{{main|Grafo ciclo}}
Un ''grafo de ciclo'' o ''grafo circular'' de orden {{nowrap|''n'' ≥ 3}} es un grafo en el que los vértices se pueden enumerar en un orden ''v''<sub>1</sub>, ''v''<sub>2</sub>, ... , ''v''<sub>''n''</sub> tal que las aristas son las {{nowrap|{{mset|''v''<sub>''i''</sub>, ''v''<sub>''i''+1</sub>}}}} donde ''i'' = 1, 2, ... , ''n'' - 1, más la arista {{nowrap|{{mset|''v''<sub>''n''</sub>, ''v''<sub>1</sub>}}}}. 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.

=== Árbol ===
{{main|Árbol (teoría de grafos)}}
Un ''árbol'' es un grafo no dirigido en el que dos [[Vértices (teoría de grafos)|vértices]] cualesquiera están conectados por ''exactamente una'' [[Camino (teoría de grafos)|trayectoria]], o equivalentemente un [[Conectividad (teoría de grafos)|conectado]] no dirigido [[Ciclo (teoría de grafos)|ací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 grafos|unión disjunta]] de árboles.

=== Poliarbol ===
{{main|Poliárbol}}

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 ===
Clases más avanzadas de grafos son:
* [[grafo de Petersen]] y sus generalizaciones;
* [[grafo perfecto]]s;
* [[cografos]];
* [[grafo cordal]]s;
* otros grafos con grandes [[Grupos de automorfismo|automorfismo de grafos]]: [[grafo transitivo de vértices|transitivo de vértices]], [[Grafo simétrico|transitivo de arcos]] y [[Grafo distancia-transitivo]];
* [[grafo fuertemente regular]] y sus generalizaciones [[grafo regular a distancia]].

== Grafos particulares ==
Existen grafos que poseen propiedades destacables. Algunos ejemplos básicos son:
* [[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 nulo|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 [[bucle (teoría de grafos)|bucles]] ni aristas paralelas. Consultar [[Grafo#Variantes_sobre_las_definiciones_principales|variantes en esta definición]].
* [[Multigrafo]] (o pseudografo): G es multigrafo [[Bicondicional|si y solo si]] no es simple. Consultar [[Grafo#Variantes_sobre_las_definiciones_principales|variantes en esta definición]].
* [[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.
* [[Grafo bipartito]]: sea <math>(W, X)</math> una [[Partición (matemática)|partición]] del conjunto de vértices <math>V</math>, es aquel donde cada arista tiene un vértice en <math>W</math> y otro en <math>X</math>.
* [[Grafo bipartito completo]]: sea <math>(W, X)</math> una [[Partición (matemática)|partición]] del conjunto de vértices <math>V</math>, es aquel donde cada vértice en <math>W</math> es adyacente ''sólo'' a cada vértice en <math>X</math>, y viceversa.
* [[Grafo plano]]: aquel que puede ser dibujado en el [[Coordenadas cartesianas|plano cartesiano]] sin cruce de aristas.
* [[Árbol (teoría de grafos)|Árbol]]: [[grafo conexo]] sin [[Grafo ciclo|ciclos]].
* [[Grafo rueda]]:  grafo con ''n'' vértices que se forma conectando un único vértice a todos los vértices de un ciclo-(''n''-1).
* [[Grafo perfecto]] aquel que el [[Coloración de grafos|número cromático]] de cada subgrafo inducido es igual al tamaño del mayor [[clique]] de ese subgrafo.

Una generalización de los grafos son los llamados [[Hipergrafo|hipergrafos]].

== Véase también ==
* [[Teoría de grafos]]
* [[Grafo social]]
* [[Grafo de conocimiento]]

== Referencias ==
{{listaref}}

== Enlaces externos ==
{{commonscat|Graphs (graph theory)}}

{{Control de autoridades}}
[[Categoría:Teoría de grafos]]
[[Categoría:Relaciones]]
[[Categoría:Invariantes de grafos]]