• Author / Uploaded
• JhonJaLopez

Citation preview

&raÍQs·

'L.

a teoría de grafos es 1m~i disciplina anrigúa con muchas aplicaciones modernas. Sus ideas _-. · , básiéas Iasintrodujoe}gi:án matén1ático suizo LeQnhard E:uler en ~-1 ~iglo xvm. Euler utilizó .. ~ - Jos grafos pa~a resolver e! famoso P!"Obl~~na de- lq~ puentes de Komgsberg, que estudiare. rµós en esie c¡ipílulo. ., -- >·. _ _ - _,. :., ,. . • _ Los.grafos fo emplean para resolver prob]em_~s de div,ersas- áreás.'Pueden utilizarse, por ejem-pJo, pi;tra determinar si sé 1:iuede, o .rio impiem.erJ.tar tiÍí cirtüito $Óbre_una placa de una sola capa. : · ' Podi n19s diferenciar_dos c~mput;stos qqíQli~os que teug~ri l;:l misma fórmula molecular, pero dis~- :·- t,ínfa ·estnicrúrit pór medjó de gráfos. Ta111 biep se pueden usar los grafos para estudjar la estrnctu• "'"ni , pero no se admiten aristas múltiples en la misma dirección entre dos vértices. Recordemos la definición.

DEFI NICIÓN 4

Un grafo dirigido (V, E) consta de un conjunto V de vé.1tices y de un conjunto E de aristas, que son pares ordenados de elementos de V. Utilizamos una flecha apuntando desde u hacia v para indicar la dirección de la arista (u , r). Finalmente, puede haber líneas múltiples en la red informática, de modo que haya varias líneas unidireccionales desde cada nodo en dfrección al ordenador de ueva York y quizá más de una línea de vuelta a cada nodo desde Nueva York, como se muestra en la figura 5. Utilizaremos multigrafos dirigidos, que pueden 1ener aristas dirigidas múltiples desde un vértice a un segundo vértice (que, eventualmente, puede coincidir con el primero), para representar este tipo de redes. Presentamos a continuación la definición formal de multigrafo dirigido.

DEFI 1ICIÓ 1 5

1

Un mulrigrafo dirigido G = (V, E) consta de un conjunto V de vértices, un conjunto E de aristas y una función/ de E en f (u, v) 1u, v e V). Se dice que tas aristas e1 y e2 son aristas múltiples sif(e 1) = f(e 2) .

San Francisco

Los Ángeles

Figura 4. Una red informática con líneas telefónicas unidireccionales.

506

Matemática discreta y sus aplicaciones

Los Ángeles

Figura 5. Una red infonnática con líneas unidireccionales múltiples.

Knlaces

El lector debería observar que las aristas dirigidas mú ltiples están asociadas a un nusmo par de vértices. No obstante, diremos que (u, v) es una arista de G = (V, E) siempre que haya al menos una arista e con f(e) = (u, v). No haremos distinciones entre la arista e y el par ordenado (u, v) a no ser que la identidad de alguna de las aristas múltiples en par ticular sea impo1t ante. La Tabla 1 resume la terminología que se emplea para los diferentes tipos de grafos. Utilizaremos Ja palabra grafo para describir grafos con aristas dirigidas o no dirigidas, con o sin bucles y aristas múltiples. Emplearemos los términos grafo no dirigido o pseudografo para indicar grafos no dirigidos que pueden tener aristas múltiples y bucles. Siempre usaremos el adjetivo dirigido al referimos a grafos cuyas aristas estén asociadas a pares ordenados. Debido a que el interés por la teoría de grafos es relativamente reciente, y a que tiene aplicaciones en disciplinas muy diversas, en la teoría de grafos se emplean muchas tenninologías distintas. Cada vez que encuentre en sus lecturas alguno de los ténninos del párrafo anterior. el lector haría bien en cercíorarse del sentido que se le da exactamente.

:MODELOS CON GRAFOS Enlaces

Los grafos se emplean en una gran variedad de modelos. Presentamos aquí unos pocos, escogidos de diversas áreas. Otros se irán presentando en secciones poste1iores, tanto de este capítulo como ele los siguientes.

EJEMPLO 1 Grafos de solapamiento de nichos en Ecología Los grafos se emplean en muchos modelos que Eu.laccs

tienen que ver con las interacciones entre especies animales distintas. Por ejemplo, la competición entre especies en un ecosistema puede representarse mediante un grafo ele solapamiento ele nichos. Cada especie se representa por un vértice. Una arista no dirigida conecta dos vértices si las dos especies representadas por esos vértices compiten entre sí (esto es, si algunas de las fuentes de alimento de las que se nutren son las mismas). El grafo de la Figura 6 representa el ecosistema de un bosque. Vemos en este grafo que las ardillas y los mapaches compíten entre sí, mientras que los cuervos y las musarañas no lo hacen. ◄

EJEMPL02 Grafos de conocidos Podemos usar modelos ele grafos para representar relaciones entre persoEnlaéÍ,s

nas. Por ejemplo, podemos usar un grafo para representar el hecho de que dos personas se conozcan. Cada pÉsona de un grupo concreto se representa mediante un vértice. Se utiliza una arista no dirigida p •~ conectar dos per_sonas cuanc!o esas dos personas se conocen. E!: la Figu~a 7 _se. muestra un peq eno grafo de conocidos. El grafo que corresponde a toda la poblaeJOn mundial tiene más de 6 mi millones de vértices y, probablemente, ¡más de un billón de aristas! Seguiremos analizando estos grafos en la Sección 8.4. ◄ Tabla l. Terminología en teoría de grafos.

Tipos Grafo simple Multigrafo Pseudografo Grafo dirigido ' Multigrafo dirigido

Aristas No dirig idas No dirigidas No dirigidat Diri gidas Dirig idas

¿Se admiten arisras múltiples No

Sí Sí No

Sí

¿Se admiren bucles? No No

Sí Sí Sí

.

,

Grafos

Mapache a,--

-

- - - - -- ----'11

507

Eduardo

Búho

K amlesh

Ching

Páj