dice que el vértice está aislado. A continuación se presenta la definición formal de un grafo. Definición Un grafo G consiste de dos conjuntos fini...

dice que el vértice está aislado. A continuación se presenta la definición formal de un grafo. Definición Un grafo G consiste de dos conjuntos finitos: un conjunto no vacío V(G) de vértices y un conjunto de aristas E(G), donde cada arista está asociada a un conjunto compuesto por uno o dos vértices llamados puntos extremos. La correspondencia de aristas a puntos finales se llama la función de arista a punto extremo. Una arista con un sólo punto extremo se llama un bucle y dos o más aristas distintas con el mismo conjunto de puntos extremos se dicen que son paralelas. Se dice que una arista conecta sus puntos finales; dos vértices que se conectan por una arista se denominan adyacentes; y un vértice que es un punto final de un bucle se dice que es adyacente a sí mismo. Se dice que una arista incide sobre cada uno de sus puntos extremos y dos aristas que inciden en el mismo punto se llaman adyacentes. Un vértice en el que no incide arista alguna se llama aislado. Las gráficas tienen representaciones pictóricas en las que los vértices se representan por puntos y las aristas por segmentos de recta. Una representación pictórica dada determina unívocamente una gráfica. Ejemplo 10.1.1 Terminología Considere la gráfica siguiente: e3 e2 e4 e6 e5 e7 e1 1 2 3 4 6 5 a. Escriba el conjunto de vértices y el conjunto de aristas y presente una tabla que muestre la función punto extremo-arista. b. Determine todas las aristas que inciden en 1, todos los vértices que son adyacentes a 1, todas las aristas adyacentes a e1, todos los bucles, todas las aristas paralelas, todos los vértices adyacentes a sí mismos y todos los vértices aislados. Solución a. conjunto de vértices { 1, 2, 3, 4, 5, 6} conjunto de aristas {e1, e2, e3, e4, e5, e6, e7} función punto extremo-arista: Arista Punto extremo-arista e1 1 2 e2 1 3 e3 1 3 e4 2 3 e5 5 6 e6 5 e7 6 Observe que el vértice aislado 4 no aparece en esta tabla. Aunque cada arista debe tener uno o dos puntos extremos, un vértice no necesita ser el punto extremo de una arista. b. e1, e2 y e3 inciden sobre 1. 2 y 3 son adyacentes a 1. e2, e3 y e4 son adyacentes a e1. e6 y e7 son bucles. e2 y e3 son paralelos. 5 y 6 son adyacentes a sí mismos. 4 es un vértice aislado. Como ya se indicó, una determinada representación pictórica determina unívocamente una gráfica. Sin embargo, una gráfica puede tener más de una representación pictórica. Cosas como las longitudes o curvaturas de las aristas y la posición relativa de los vértices en la página pueden variar de una representación a otra. Ejemplo 10.1.2 Dibujo de más de una imagen de una gráfica Considere la gráfica que se especifica de la forma siguiente: conjunto de vértices { 1, 2, 3, 4} conjunto de aristas {e1, e2, e3, e4} función punto extremo-arista: Arista Puntos extremos e1 1 3 e2 2 4 e3 2 4 e4 3 Los dos dibujos a) y b) que se muestran a continuación son representaciones pictóricas de esta gráfica. e4 e1 e2 e2 e4 e3 e1 e3 3 4 5 2 1 3 4 a) b) Ejemplo 10.1.3 Etiquetado de dibujos para demostrar que representan la misma gráfica Considere los dos dibujos que se muestran en la figura 10.1.1. Etiquete los vértices y las aristas de tal manera que ambos dibujos representen la misma gráfica. a) b) Figura 10.1.1 Solución Imagine poner el extremo de un pedazo de cuerda en el vértice superior de la figura 10.1.1a) (llame a este vértice 1), después la cuerda cae al siguiente vértice adyacente en la parte inferior derecha (llame a este vértice 2), después cae al siguiente vértice adyacente la parte superior izquierda ( 3) y así sucesivamente, regresando finalmente al vértice superior 1. Llame a la primera arista e1, a la segunda e2 y así sucesivamente, como se muestra a continuación. e3 e1 e4 e2 e5 3 4 5 2 1 Ahora imagine juntar el pedazo de cuerda, junto con sus etiquetas y cambiar a la posición siguiente: e3 e1 e4 e2 4 1 5 2 3 e5 Ésta es igual a la figura 10.1.1b), por lo que ambos dibujos son representaciones de la gráfica con conjunto de vértices { 1, 2, 3, 4, 5}, conjunto de aristas {e1, e2, e3, e4, e5} y la función de punto extremo-arista como sigue: Arista Punto extremo-arista e1 1 2 e2 2 3 e3 3 4 e4 4 5 e5 5 1 En el capítulo 8 analizamos el grafo dirigido de una relación binaria sobre un conjunto. La definición general de grafo dirigido es similar a la definición de grafo, salvo que se asocia un par ordenado de vértices a cada arista en lugar de un conjunto de vértices. Así cada arista de un grafo dirigido se puede dibujar como una flecha que va del primer vértice al segundo vértice del par ordenado. Definición Un grafo dirigido o digráfica, consiste en dos conjuntos finitos: un conjunto no vacío V(G) de vértices y un conjunto de aristas dirigidas D(G), donde cada uno está asociado con un par ordenado de vértices llamado sus puntos extremos. Si el arista e está asociada con el par de vértices ( , ), entonces se dice que e es la arista (dirigida) de a . Observe que cada grafo dirigido tiene un grafo (no dirigido) ordinario asociado, que se obtiene ignorando las direcciones de las aristas. Ejemplos de grafos Los grafos son una poderosa herramienta para resolver problemas ya que nos permiten representar una situación compleja con una sola imagen que puede analizarse tanto visualmente y con la ayuda de una computadora. A continuación presentamos unos pocos ejemplos y en los ejercicios se incluyen otros. Ejemplo 10.1.4 Uso de un grafo para representar una red Telefonía, energía eléctrica, tuberías de gas y sistemas de transporte aéreo todos se pueden representar mediante grafos, como redes de computadoras, desde una red pequeña de área local al sistema mundial de internet que conecta a millones de computadoras en todo el mundo. Cuestiones que se plantean en el diseño de estos sistemas implican elegir aristas conectadas para minimizar los costos, optimizar un cierto tipo de servicio, etcétera. En la siguiente página, se muestra una red típica llamada un modelo radial. Boston Nueva York Washington Chicago Denver San Francisco Los Ángeles Ejemplo 10.1.5 Uso de un grafo para representar a la red mundial La red mundial (World Wide Web, www), o web, es un sistema de documentos vinculados entre sí, o páginas web, contenidas en el internet. Los usuarios empleando exploradores web, como internet Explorer, Google Chrome, Apple Safari y Opera, puede pasar rápidamente de una página web a otra haciendo clic en los hipervínculos, que utilicen versiones de software llamados protocolos de transferencia de hipertexto (HTTP). Las personas y las empresas particulares crean páginas, que transmiten a los servidores que contienen software capaz de enviarlas a quienes las solicitan a través de un navegador web. Debido a que la cantidad de información en la web es muy vasta, motores de búsqueda como Google, Yahoo y Bing, tienen algoritmos para encontrar información muy eficientemente. La siguiente imagen muestra una fracción de minuto de las conexiones de hipervínculo en el internet que radian hacia dentro y hacia fuera de la página principal de Wikipedia. W ik ip ed ia /C hr is 7 3 Ejemplo 10.1.6 Uso de un grafo para representar conocimiento En muchas aplicaciones de inteligencia artificial, se recopila una base de conocimientos de información y se representa en una computadora. Debido a la forma del conocimiento se representa y debido a las propiedades que rigen el programa de inteligencia artificial, la computadora no se limita a recuperar los datos de la misma forma