Grafo
6
4
3
Grafo etiquetado con 6 vrtices y 7 aristas.
Los siete puentes de Knigsberg.
En matemticas y ciencias de la computacin, un grafo
(del griego grafos: dibujo, imagen) es un conjunto de objetos llamados vrtices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones
binarias entre elementos de un conjunto.[1] Son objeto de
estudio de la teora de grafos.
une ambas islas. El problema planteaba lo siguiente: es
posible dar un paseo comenzando desde cualquiera de estas regiones, pasando por todos los puentes, recorriendo
solo una vez cada uno y regresando al mismo punto de
Tpicamente, un grafo se representa grcamente como partida?
un conjunto de puntos (vrtices o nodos) unidos por lneas
Abstrayendo este problema y plantendolo con la (enton(aristas).
ces an bsica) teora de grafos, Euler consigue demostrar
Desde un punto de vista prctico, los grafos permiten es- que el grafo asociado al esquema de puentes de Knigstudiar las interrelaciones entre unidades que interactan berg no tiene solucin, es decir, no es posible regresar al
unas con otras. Por ejemplo, una red de computadoras vrtice de partida sin pasar por alguna arista dos veces.
puede representarse y estudiarse mediante un grafo, en el
De hecho, Euler resuelve el problema ms general: qu
cual los vrtices representan terminales y las aristas reprecondiciones debe satisfacer un grafo para garantizar que
sentan conexiones (las cuales, a su vez, pueden ser cables
se puede regresar al vrtice de partida sin pasar por la
o conexiones inalmbricas).
misma arista ms de una vez? Si denimos como grado
Prcticamente cualquier problema puede representarse al nmero de lneas que se encuentran en un punto de un
mediante un grafo, y su estudio trasciende a las diversas grafo, entonces la respuesta al problema es que los puentes
reas de las ciencias exactas y las ciencias sociales.
de un pueblo se pueden atravesar exactamente una vez si,
salvo a lo sumo dos, todos los puntos tienen un grado par.
Historia y problema de los puen2 Deniciones
tes de Knigsberg
Un grafo G es un par ordenado G = (V, E) , donde:
El primer artculo cientco relativo a grafos fue escrito por el matemtico suizo Leonhard Euler en 1736. Eu V es un conjunto de vrtices o nodos, y
ler se bas en su artculo en el problema de los puentes
E es un conjunto de aristas o arcos, que relacionan
de Knigsberg. La ciudad de Kaliningrado, originalmenestos nodos.
te Knigsberg, es famosa por sus siete puentes que unen
ambas mrgenes del ro Pregel con dos de sus islas. Dos
de los puentes unen la isla mayor con la margen oriental y Normalmente V suele ser nito. Muchos resultados imotros dos con la margen occidental. La isla menor est co- portantes sobre grafos no son aplicables para grafos innectada a cada margen por un puente y el sptimo puente nitos.
1
4 EJEMPLOS
Se llama orden del grafo G a su nmero de vrtices, |V | Por denicin, los grafos dirigidos no contienen bucles.
.
Un grafo mixto es aquel que se dene con la capacidad
El grado de un vrtice o nodo v V es igual al nmero de poder contener aristas dirigidas y no dirigidas. Tanto
de arcos que lo tienen como extremo.
los grafos dirigidos como los no dirigidos son casos particulares de este.
Un bucle es una arista que relaciona al mismo nodo; es
decir, una arista donde el nodo inicial y el nodo nal coinciden.
2.3 Variantes sobre las deniciones princiDos o ms aristas son paralelas si relacionan el mismo par
de vrtices.
2.1
Grafo no dirigido
Grafo no dirigido
Un grafo no dirigido o grafo propiamente dicho es un
grafo G = (V, E) donde:
pales
Algunas aplicaciones requieren extensiones ms generales a las dos propuestas clsicas de grafos. Aunque la denicin original los permite, segn la aplicacin concreta
pueden ser vlidos o no. A veces V o E pueden ser un
multiconjunto, pudiendo haber ms de una arista entre
cada par de vrtices. La palabra grafo (a secas) puede
permitir o no mltiples aristas entre cada par de vrtices,
dependiendo del autor de la referencia consultada. Si se
quiere remarcar la inexistencia de mltiples aristas entre cada par de vrtices (y en el caso no dirigido, excluir
bucles) el grafo puede llamarse simple. Por otra parte,
si se quiere asegurar la posibilidad de permitir mltiples
aristas, el grafo puede llamarse multigrafo (a veces se
utiliza el trmino pseudografo para indicar que se permiten tanto bucles como mltiples aristas entre cada par
de vrtices).
V =
E {x P(V ) : |x| = 2} es un conjunto de
pares no ordenados de elementos de V .
Un par no ordenado es un conjunto de la forma {a, b}
, de manera que {a, b} = {b, a} . Para los grafos, estos
conjuntos pertenecen al conjunto potencia de V , denotado P(V ) , y son de cardinalidad 2.
2.2
Grafo dirigido
3 Propiedades
Adyacencia: dos aristas son adyacentes si tienen un
vrtice en comn, y dos vrtices son adyacentes si
una arista los une.
Incidencia: una arista es incidente a un vrtice si
sta lo une a otro.
Ponderacin: corresponde a una funcin 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 optimizacin, como
el del vendedor viajero o del camino ms corto.
Etiquetado: distincin que se hace a los vrtices y/o
aristas mediante una marca que los hace unvocamente distinguibles del resto.
Grafo dirigido
Un grafo dirigido o digrafo es un grafo G = (V, E)
donde:
4 Ejemplos
La imagen es una representacin del siguiente grafo:
V =
E {(a, b) V V : a = b} es un conjunto de
pares ordenados de elementos de V .
V:={1,2,3,4,5,6}
E:={{1,2},{1,5},{2,3},{2,5},{3,4},{4,5},{4,6}}
Dada una arista (a, b) , a es su nodo inicial y b su nodo El hecho que el vrtice 1 sea adyacente con el vrtice 2
nal.
puede ser denotado como 1 ~ 2.
3
Grafo plano: aquel que puede ser dibujado en el
plano cartesiano sin cruce de aristas.
6
4
rbol: grafo conexo sin ciclos.
En la teora de las categoras una categora puede
ser considerada como un multigrafo dirigido, con
los objetos como vrtices y los morsmos como aristas dirigidas.
En ciencias de la computacin los grafos dirigidos
son usados para representar mquinas de estado nito y algunas otras estructuras discretas.
Una relacin binaria R en un conjunto X es un grafo
dirigido simple. Dos vrtices a, b en X estn conectados por una arista dirigida ab si aRb.
Grafo rueda: grafo con n vrtices que se forma conectando un nico vrtice a todos los vrtices de un
ciclo-(n1).
Grafo perfecto aquel que el nmero cromtico de
cada subgrafo inducido es igual al tamao del mayor
clique de ese subgrafo.
Una generalizacin de los grafos son los llamados
hipergrafos.
6 Referencias
[1] Trudeau, Richard J. (1993). Dover Pub., ed. Introduction
to Graph Theory (Edicin corregida y aumentada.). ISBN
978-0-486-67870-2.
7 Vase tambin
Portal:Matemtica. Contenido relacionado con
Matemtica.
Portal:Geometra. Contenido relacionado con
Geometra.
Grafos particulares
Existen grafos que poseen propiedades destacables. Algunos ejemplos bsicos son:
Grafo nulo: aquel que no tiene vrtices ni aristas.
Ntese que algunas personas exigen que el conjunto
de vrtices no sea vaco en la denicin de grafo.
Grafo vaco: aquel que no tiene aristas.
Grafo trivial: aquel que tiene un vrtice y ninguna
arista.
Grafo simple: aquel que no posee bucles ni aristas
paralelas. Consultar variantes en esta denicin.
Multigrafo (o pseudografo): G es multigrafo si y solo si no es simple. Consultar variantes en esta denicin.
Grafo completo: grafo simple en el que cada par de
vrtices estn unidos por una arista, es decir, contiene todas las posibles aristas.
Grafo bipartito: sea (W, X) una particin del conjunto de vrtices V , es aquel donde cada arista tiene
un vrtice en W y otro en X .
Grafo bipartito completo: sea (W, X) una particin
del conjunto de vrtices V , es aquel donde cada vrtice en W es adyacente slo a cada vrtice en X , y
viceversa.
Grafo social
Teora de grafos
8 Enlaces externos
Wikimedia Commons alberga contenido multimedia sobre Grafo. Commons
9 ORIGEN DEL TEXTO Y LAS IMGENES, COLABORADORES Y LICENCIAS
Origen del texto y las imgenes, colaboradores y licencias
9.1
Texto
Grafo Fuente: [Link] Colaboradores: Pino, Oblongo, Moriel, Juan M Taboada, Ascnder,
Tano4595, La Mantis, Digigalos, AlfonsoERomero, Dromero, Yrbot, BOTijo, Armin76, KnightRider, Txo, Baneld, Er Komandante, Juan
Marquez, Ilan.ag1, Kn, BOTpolicia, CEM-bot, Laura Fiorucci, AndresDominguez, Baiji, Mcetina, Fsd141, Thijs!bot, Roberto Fiadone,
RoyFocker, Max Changmin, ngel Luis Alfaro, Jtoselli, Botones, Mpeinadopa, JAnDbot, Wybot, TXiKiBoT, Ignacioerrico, Cinevoro,
Acosta89, Matdrodes, Muro Bot, Manuc82, Meldor, SieBot, Farisori, LordT, Rrupo, UA31, AVBOT, Ellinik, MastiBot, Adelpine, Diegusjaimes, Arjuno3, Luckas-bot, Jotterbot, DirlBot, Jkbw, Rilog, Paladium, AlemanI2.0, PatruBOT, KamikazeBot, TjBot, Ripchip Bot,
CentroBabbage, Gulliberto, GrouchoBot, Sergio Andres Segovia, CocuBot, MerlIwBot, UAwiki, Addihockey10 (automated), Bxs3, RosenJax, Makecat-bot, YFdyh-bot, Keyla Herrera Ruiz, Addbot, Zhirose, CAPTAIN RAJU y Annimos: 57
9.2
Imgenes
Archivo:[Link] Fuente: [Link] Licencia: Public domain Colaboradores:
Image:[Link] simlar input data Artista original: User:AzaToth
Archivo:Commons-emblem-question_book_orange.svg
Fuente:
[Link]
Commons-emblem-question_book_orange.svg Licencia: CC BY-SA 3.0 Colaboradores: <a href='//[Link]/wiki/File:
[Link]' class='image'><img alt='[Link]' src='[Link]
commons/thumb/b/bc/[Link]/[Link]' width='25' height='25' srcset='https:
//[Link]/wikipedia/commons/thumb/b/bc/[Link]/[Link]
1.5x,
[Link] 2x'
data-le-width='48' data-le-height='48' /></a> + <a href='//[Link]/wiki/File:Question_book.svg' class='image'><img
alt='Question
[Link]'
src='[Link]
[Link]' width='25' height='20' srcset='[Link]
38px-Question_book.[Link] 1.5x, [Link]
[Link] 2x' data-le-width='252' data-le-height='199' /></a> Artista original: GNOME icon artists, Jorge 2701
Archivo:[Link] Fuente: [Link] Licencia: Public domain Colaboradores: This version created by Pumbaa, using a proper partial circle and SVG geometry features. (Former versions used
to be slightly warped.) Artista original: SVG version was created by User:Grunt and cleaned up by 3247, based on the earlier PNG version,
created by Reidab.
Archivo:Kaari_suunnattu_graafiteoria.png
Fuente:
[Link]
[Link] Licencia: Public domain Colaboradores: ? Artista original: ?
Archivo:Kaari_suuntaamaton_graafiteoria.png
Fuente:
[Link]
suuntaamaton_graafiteoria.png Licencia: Public domain Colaboradores: ? Artista original: ?
Archivo:Konigsberg_bridges.png Fuente: [Link] Licencia:
CC-BY-SA-3.0 Colaboradores: Public domain (PD), based on the image
<a
href='//[Link]/wiki/File:Image-Koenigsberg,_Map_by_Merian-Erben_1652.jpg'
class='image'><img
alt='Image-Koenigsberg, Map by Merian-Erben [Link]' src='[Link]
Image-Koenigsberg%2C_Map_by_Merian-Erben_1652.jpg/120px-Image-Koenigsberg%2C_Map_by_Merian-Erben_1652.jpg'
width='120'
height='84'
srcset='[Link]
2C_Map_by_Merian-Erben_1652.jpg/180px-Image-Koenigsberg%2C_Map_by_Merian-Erben_1652.jpg
1.5x,
https:
//[Link]/wikipedia/commons/thumb/1/15/Image-Koenigsberg%2C_Map_by_Merian-Erben_1652.jpg/
240px-Image-Koenigsberg%2C_Map_by_Merian-Erben_1652.jpg 2x' data-le-width='628' data-le-height='437' /></a>
Artista original: Bogdan Giuc
Archivo:Nuvola_apps_edu_mathematics-[Link] Fuente: [Link]
[Link] Licencia: GPL Colaboradores: Derivative of Image:Nuvola apps edu [Link] created by self Artista original:
David Vignoni (original icon); Flamurai (SVG convertion)
Archivo:[Link] Fuente: [Link] Licencia: CC BY 2.5 Colaboradores:
[Link]
Artista original: [Link]: Pepetps
9.3
Licencia del contenido
Creative Commons Attribution-Share Alike 3.0
