Apuntes de Teoría de Grafos — Matemática Discreta UAB

Y 0 flashcards y 12 preguntas más en el documento.

Texto del documento

APUNTES MATEMÁTICA DISCRETA Grado en Ingeniería Informática Universidad Autónoma de Barcelona AprenAI 2026-2027 Resumen de teoría de grafos: conectividad, Euler, Hamilton, árboles, Kruskal y Prim para Matemática Discreta del Grado en Ingeniería Informática.

APREN.AI Índice Fundamentos de grafos 1 Conceptos básicos y tipos de grafos Modelado computacional mediante grafos Definición matemática de grafo simple Variantes de grafos: multigrafos, pseudografos y pesos Grafos dirigidos (digrafos) 2 Familias especiales de grafos y topologías de red Grafos completos y grafos nulos Ciclos y grafos rueda Hipercubos (Qn) Grafos bipartitos y bipartitos completos Modelado de topologías en redes de área local 3 Representación matricial y subgrafos Representación matricial de grafos Concepto general de subgrafo y variantes Operaciones de eliminación de elementos y grafo complementario 4 Grados de vértices e isomorfismo Grado de un vértice y propiedades fundamentales El lema del apretón de manos Grafos regulares Isomorfismo de grafos Invariantes de isomorfismo y protocolo de descarte Conectividad en grafos 5 Recorridos, distancias y componentes conexas Secuencias de vértices y aristas: recorridos Taxonomía estricta de recorridos abiertos y cerrados Propiedades métricas: distancia y diámetro Grafos conexos, relación de equivalencia y componentes 6 Aristo-conectividad y vértice-conectividad Robustez y vulnerabilidad en redes conexas Aristas puente y aristo-conectividad Vértices de corte y vértice-conectividad La desigualdad de Whitney Apuntes de Teoría de Grafos — Matemática Discreta UAB 1 Rutas en grafos 7 Circuitos eulerianos y algoritmo de Fleury El problema histórico de los puentes de Königsberg Circuitos de Euler, cadenas de Euler y grafos eulerianos Teorema de caracterización de grafos eulerianos Teorema de caracterización de cadenas eulerianas Algoritmo de Fleury 8 Ciclos hamiltonianos y condiciones de existencia Origen histórico y definiciones fundamentales Contraste con los circuitos eulerianos Criterios de descarte para la no existencia de ciclos hamiltonianos Condiciones suficientes: Teoremas de Ore y Dirac Árboles y recorridos 9 Propiedades fundamentales y caracterizaciones Definición y propiedades extremales Teorema fundamental de caracterización de árboles Árboles generadores en grafos conexos Estrategias básicas de construcción 10 Búsqueda en profundidad (DFS) y en anchura (BFS) Búsqueda en profundidad (DFS) Corrección teórica del algoritmo DFS Traza paso a paso de DFS Búsqueda en anchura (BFS) y cálculo de distancias Traza comparativa de BFS 11 Árboles generadores ponderados — Algoritmos de Kruskal y Prim El problema del árbol generador mínimo (MST) Algoritmo de Kruskal: selección global sin ciclos Demostración de optimalidad de Kruskal Algoritmo de Prim: crecimiento de corte conexo Demostración de optimalidad de Prim Comparación operativa entre Kruskal y Prim 12 Árboles con raíz — Estructura jerárquica y árboles de decisión Estructura y jerarquía de los árboles con raíz Cota inferior de la altura en árboles m-arios Árboles de decisión y el problema de la pesada de monedas Cota inferior para algoritmos de ordenación por comparación 13 Formulario Invariantes y familias fundamentales de grafos Apuntes de Teoría de Grafos — Matemática Discreta UAB 2 Conectividad y desigualdad de Whitney Recorridos eulerianos y hamiltonianos Árboles y optimización Errores típicos Soluciones de las preguntas de repaso Estos apuntes pueden contener errores u omisiones.

Son un material de apoyo y no sustituyen al temario oficial ni al profesorado: contrasta la información importante. Apuntes de Teoría de Grafos — Matemática Discreta UAB 3 1 Conceptos básicos y tipos de grafos AL ACABAR SABRÁS Diferenciar formalmente un grafo simple de multigrafos, pseudografos y grafos dirigidos. Determinar con precisión el orden y el tamaño de cualquier grafo a partir de sus conjuntos fundamentales. Modelar problemas reales de redes, tráfico y proyectos asignando vértices, aristas y arcos de forma adecuada. PIÉNSALO ANTES DE LEER 1 ¿Por qué un mapa de calles de sentido único no puede representarse con un grafo simple ordinario?

La teoría de grafos proporciona un marco formal para analizar relaciones entre elementos discretos mediante nodos e interconexiones. Fundamentos de grafos 1 Conceptos básicos y tipos de grafos 2 Familias especiales de grafos y topologías de red 3 Representación matricial y subgrafos 4 Grados de vértices e isomorfismo Apuntes de Teoría de Grafos — Matemática Discreta UAB 4 ESQUEMA Estructura del tema: Fundamentos de grafos Modelado computacional mediante grafos Diversos problemas de ingeniería y ciencias aplicadas encuentran una descripción natural mediante grafos: Planificación de proyectos: Permite organizar conjuntos de actividades interdependientes.

Los grafos orientados modelan la prelación y precedencia de tareas complejas. Sistemas de tráfico: Los cruces e intersecciones urbanas corresponden a vértices, mientras que los tramos viales actúan como aristas. Una calle de doble sentido se modela con aristas no dirigidas, y una vía de sentido único mediante aristas dirigidas. Este enfoque ayuda a identificar puntos negros y a simular variaciones de flujo vehicular. Redes de ordenadores: Las computadoras y dispositivos periféricos funcionan como vértices, enlazados mediante aristas que representan canales de comunicación. El análisis del grafo permite optimizar la eficiencia y evaluar la fiabilidad de la red.

Otras disciplinas: Se emplean en la distinción de estructuras moleculares con idéntica fórmula química o en la verificación de circuitos de diseño plano. Definición matemática de grafo simple Formalmente, un grafo simple es una estructura matemática denotada por el par , donde es un conjunto no vacío de vértices y es un conjunto de aristas. DEFINICIÓN Un grafo simple satisface que cada arista es un conjunto de dos vértices distintos con y . Al tratarse de un par no ordenado, la notación abreviada equivale a .

Dos parámetros fundamentales determinan el tamaño estructural de un grafo: Definiciones y tipos Grafos simples, no dirigidos y digrafos Familias especiales Completos, ciclos, bipartitos y cubos Representación y subgrafos Matrices de adyacencia e incidencia Grados e isomorfismo Lema apretón de manos y equivalencias G = (V , E) V E G = (V , E) e = {x, y} x, y V x = y xy yx Apuntes de Teoría de Grafos — Matemática Discreta UAB 5 Orden: Corresponde al número total de vértices, expresado por el cardinal "V". Tamaño: Representa la cantidad de aristas, denotado por el cardinal "E". Cuando existe una arista , se dice que es incidente a los vértices e , a los que une conectándolos.

Los vértices e reciben el nombre de extremos de la arista, y se denominan vértices adyacentes o vecinos entre sí. EJEMPLO Consideremos el grafo definido por los conjuntos: Este grafo posee un orden de y un tamaño de . Gráficamente, los cuatro elementos se representan mediante puntos en el plano y los cinco pares de aristas mediante líneas continuas que los vinculan. COMPRUEBA 2 ¿Por qué la arista {1, 2} y la arista {2, 1} describen la misma entidad en un grafo simple? Variantes de grafos: multigrafos, pseudografos y pesos Al relajar las restricciones de los grafos simples surgen estructuras más generales para modelar escenarios con conexiones repetidas o bucles reflexivos.

Multigrafos Un multigrafo consta de un conjunto de vértices, un conjunto de aristas y una función de incidencia que asigna a cada arista un par no ordenado de vértices distintos: Dos aristas distintas y son aristas múltiples o paralelas cuando comparten los mismos extremos, es decir, cuando . A diferencia del grafo simple, donde entre dos nodos solo puede existir a lo sumo una arista, el multigrafo admite varias conexiones paralelas entre el mismo par de extremos. Pseudografos Un pseudografo constituye el modelo más general dentro de los grafos no dirigidos.

Se define como la terna o par formal con una función de incidencia que no restringe la igualdad de los extremos: Si una arista cumple que f(e) = uu = \{u\} para algún nodo , se clasifica como bucle (o lazo). Un pseudografo permite simultáneamente la presencia de bucles y de aristas múltiples.

e = xy e x y x y G = (V , E) V = {1, 2, 3, 4} E = {{1, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 4}} V = 4 E = 5 G = (V , E) V E f f : E {uv u, v V , u = v} e 1 e 2 f(e ) = 1 f(e ) 2 f : E {uv u, v V } e u V Apuntes de Teoría de Grafos — Matemática Discreta UAB 6 Grafos ponderados Un grafo ponderado enriquece la estructura al incorporar una aplicación de valoración métrica o de coste sobre las conexiones: DEFINICIÓN Un grafo ponderado es una terna compuesta por un grafo y una función de ponderación que asocia a cada arista un número real positivo denominado peso. COMPRUEBA 3 ¿Qué diferencia técnica distingue a un multigrafo de un pseudografo?

Grafos dirigidos (digrafos) En múltiples situaciones prácticas las conexiones imponen una dirección obligatoria. Un grafo dirigido o digrafo formaliza esta condición. DEFINICIÓN Un digrafo consta de un conjunto no vacío de vértices y un conjunto de arcos (o aristas dirigidas), donde cada elemento de es un par ordenado de vértices de . Gráficamente, los arcos se dibujan mediante flechas que apuntan desde el vértice inicial u origen hacia el vértice final o destino. Dado un conjunto de vértices y arcos , el par designa un trayecto orientado de hacia , el cual es conceptual y funcionalmente distinto del arco . Tipo de Grafo Naturaleza de las aristas ¿Admite múltiples aristas? ¿Admite bucles?

Grafo simple Pares no ordenados con No No Multigrafo Pares no ordenados asignados por con Sí No Pseudografo Pares no ordenados asignados por Sí Sí Grafo dirigido (digrafo) Pares ordenados No (en digrafos simples) Sí (pares ) G = (V , E, w) w : E R+ e w(e) D = (V , A) V A A V V = {x, y, v, w} A = {(v, w), (w, y), (y, x), (x, v)} (v, w) v w (w, v) {u, v} u = v f(e) u = v f(e) (u, v) (u, u) Apuntes de Teoría de Grafos — Matemática Discreta UAB 7 ERROR FRECUENTE Confundir un par no ordenado con un par ordenado al definir aristas. En un grafo no dirigido simple, y representan exactamente la misma arista.

En cambio, en un digrafo, el arco no equivale a , pues establecen sentidos de circulación opuestos. Asimismo, asumir la presencia de bucles en un grafo simple invalida los cálculos de adyacencia y tamaño, ya que los extremos de una arista simple deben ser siempre distintos. COMPRUEBA 4 Si un digrafo contiene el arco (x, y), ¿significa necesariamente que también existe comunicación de y hacia x? IDEAS CLAVE Un grafo simple está constituido por un conjunto no vacío de vértices y aristas representadas como pares no ordenados de vértices distintos. El orden de un grafo corresponde al cardinal y el tamaño al cardinal de aristas .

Un multigrafo permite aristas múltiples o paralelas entre dos vértices mediante una función de incidencia, pero excluye bucles. Un pseudografo es la forma más general no dirigida y autoriza tanto aristas paralelas como bucles incidentes en un solo vértice. Un grafo ponderado asocia a cada arista un valor real positivo denominado peso a través de una función . Un digrafo utiliza pares ordenados de vértices denominados arcos, diferenciando la dirección del trayecto entre el origen y el destino. COMPRUEBA LO QUE HAS APRENDIDO 5. En un grafo simple con vértices {A, B, C}, ¿cuántas aristas como máximo pueden conectar al par de vértices A y B? 6.

Si una arista e en un pseudografo cumple f(e) = {v}, ¿cómo se clasifica dicha arista y cuántos extremos distintos posee? {u, v} {v, u} (u, v) (v, u) G = (V , E) V E w : E R+ Apuntes de Teoría de Grafos — Matemática Discreta UAB 8 FUNDAMENTOS DE GRAFOS 2 Familias especiales de grafos y topologías de red AL ACABAR SABRÁS Calcular el orden y tamaño de grafos completos, ciclos, ruedas e hipercubos mediante sus expresiones analíticas. Demostrar formalmente la condición de bipartición en hipercubos a partir de la paridad binaria. Asociar cada topología de red de área local con su correspondiente modelo teórico en teoría de grafos.

PIÉNSALO ANTES DE LEER 7 ¿Por qué una red local configurada como rueda es más tolerante a fallos que un anillo simple? Grafos completos y grafos nulos Determinadas estructuras de grafos simples aparecen de manera recurrente en problemas teóricos y prácticos (véase «Fundamentos de grafos — Conceptos básicos y tipos de grafos» para la noción de grafo simple). Dos familias elementales representan los casos extremos de conectividad: DEFINICIÓN Para todo entero positivo , un grafo completo, denotado por , es un grafo simple de orden donde cada par de vértices distintos está conectado por una arista.

Su opuesto estructural es el grafo nulo , un grafo de orden con conjunto de vértices y ninguna arista. Dado que en existe exactamente una arista por cada subconjunto de dos vértices distintos, el cálculo del número total de aristas se obtiene mediante combinatoria básica: En contraposición directa, el grafo nulo contiene aristas. Como caso particular, para coinciden ambas definiciones: y representan el vértice aislado con cero aristas. COMPRUEBA 8 ¿Cuántas aristas tiene un grafo completo K y cuántas tiene un grafo nulo N ? Ciclos y grafos rueda Cuando los vértices forman una secuencia cerrada continua sin ramificaciones, se obtiene la familia de ciclos: n K n n N n n V = {v , v , …

, v } 1 2 n K n E = = ( 2 n ) 2 n(n 1) N n E = 0 n = 1 K 1 N 1 Apuntes de Teoría de Grafos — Matemática Discreta UAB 9 DEFINICIÓN Si es un entero, el grafo ciclo posee como vértices y como aristas . Un ciclo posee exactamente vértices y aristas. Cada vértice está conectado a dos vecinos inmediatos. A partir del ciclo se construye la familia de grafos rueda, denotada por . Para , el grafo se genera añadiendo un vértice adicional externo al ciclo base y uniendo este nuevo centro a cada uno de los vértices periféricos mediante aristas radiales. ERROR FRECUENTE Confundir el subíndice del grafo rueda con su orden total.

El grafo tiene orden vértices y tamaño aristas, ya que proviene de conectar un vértice central a los vértices del ciclo (que ya aportaba aristas). Por ejemplo, tiene 4 vértices y 6 aristas, coincidiendo con . COMPRUEBA 9 ¿Cuál es el orden y el tamaño del grafo rueda W ? Hipercubos (Qn) La familia de hipercubos modela estructuras de conmutación digital y comunicaciones en paralelo: DEFINICIÓN El hipercubo de dimensión , denotado por , es el grafo cuyos vértices corresponden a las cadenas binarias de longitud . Dos vértices son adyacentes si y sólo si sus cadenas binarias asociadas difieren en exactamente una posición (distancia de Hamming igual a 1).

Analicemos las primeras dimensiones de esta familia: : Posee vértices (0 y 1) y 1 arista que los une. Coincide con . : Posee vértices (00, 01, 11, 10) y 4 aristas formando un cuadrado. Coincide con . : Posee vértices y 12 aristas dispuestas como los vértices y aristas de un cubo tridimensional estándar. En general, cada vértice de puede modificar cualquiera de sus bits para generar un vecino. Como consecuencia directa, cada uno de sus vértices tiene grado , arrojando un total de aristas. COMPRUEBA 10 ¿Son adyacentes los vértices 101 y 110 en el hipercubo Q ? n 3 C n V = {v , v , … , v } 1 2 n E = {{v , v }, {v , v }, …

, {v , v }, {v , v }} 1 2 2 3 n 1 n n 1 C n n n W n n 3 W n C n n n W n n + 1 2n n C n n W 3 K 4 n Q n 2n n Q 1 2 = 1 2 K 2 Q 2 2 = 2 4 C 4 Q 3 2 = 3 8 Q n n 2n n n2n 1 Apuntes de Teoría de Grafos — Matemática Discreta UAB 10 Grafos bipartitos y bipartitos completos La noción de bipartición surge al separar los elementos de un sistema en dos categorías incompatibles internamente: DEFINICIÓN Un grafo simple es bipartito si su conjunto de vértices puede dividirse en dos subconjuntos disjuntos no vacíos y ( , con ) tales que toda arista de une un vértice de con un vértice de . En consecuencia, no existen aristas entre vértices del mismo subconjunto.

Si además se incluye la totalidad de las conexiones posibles entre ambos bloques, se obtiene un grafo bipartito completo, denotado como . En este grafo, cada elemento de (con ) se une mediante una arista a todos y cada uno de los elementos de (con ). El número total de aristas en es el producto . Los hipercubos ilustran con claridad la bipartición: Bipartición en : Clasificando los vértices según la paridad del número de unos en su representación binaria, situamos en las cadenas con peso par y en las de peso impar. Cada cambio de un solo bit conmuta la paridad, de modo que toda arista conecta forzosamente un vértice de con uno de . Por ello, es un grafo bipartito.

Isomorfismo de : En dos dimensiones, y . Cada uno de los dos vértices de está enlazado con los dos de , lo que demuestra que es equivalente al bipartito completo . COMPRUEBA 11 ¿Cuántos vértices y cuántas aristas posee el grafo bipartito completo K , ? Modelado de topologías en redes de área local Las familias especiales de grafos proporcionan abstracciones directas para desplegar redes locales cableadas donde terminales, servidores e impresoras intercambian información: Topología de red Familia de grafos Características del tráfico Fiabilidad y redundancia Estrella Bipartito completo Todo mensaje pasa obligatoriamente por el nodo central de control.

Vulnerable a fallos en el centro; sin rutas alternativas. G = (V , E) V 1 V 2 V = V 1 V 2 V 1 V = 2 E V 1 V 2 K n ,n 1 2 V1 V = 1 n 1 V 2 V = 2 n 2 K n ,n 1 2 E = n 1 n 2 Q 3 V = 1 {000, 011, 101, 110} V = 2 {001, 010, 100, 111} V 1 V 2 Q 3 Q 2 V = 1 {00, 11} V = 2 {01, 10} V 1 V 2 Q 2 K 2,2 K 1,n Apuntes de Teoría de Grafos — Matemática Discreta UAB 11 Topología de red Familia de grafos Características del tráfico Fiabilidad y redundancia Anillo Ciclo La información viaja de nodo en nodo por el perímetro cerrado. Baja redundancia; la caída de un enlace interrumpe el recorrido unidireccional. Híbrida Grafo rueda El tráfico puede fluir por el ciclo exterior o a través del centro.

Alta fiabilidad; la redundancia de enlaces evita el aislamiento ante averías. ESQUEMA Familias especiales de grafos En la topología en estrella, modelada como , el conjunto consta de un único dispositivo central (conmutador o concentrador) y contiene los puestos periféricos. Los extremos no se comunican de forma directa, sino que delegan el reenvío en el nodo coordinador. En la topología en anillo, modelada mediante , cada equipo está acoplado exactamente con otros dos vecinos. La información circula secuencialmente a lo largo del bucle hasta alcanzar la estación de destino requerida. Para paliar las debilidades de ambas opciones, la topología híbrida adopta la estructura de una rueda .

Los datos disponen de caminos alternativos: pueden circular por la periferia del ciclo o atajar hacia el núcleo central. Dicha redundancia confiere a la red una tolerancia muy superior frente a caídas de enlaces o nodos intermedios. C n W n Grafos simples notables Estructuras canónicas regulares y bipartitas Extremos de densidad K_n completo y N_n nulo Estructuras circulares C_n anillo y W_n rueda Hipercubos Q_n Cadenas binarias con distancia 1 Partición bipartita Bipartitos y completos K_{n1,n2} K 1,n V 1 V 2 n C n W n Apuntes de Teoría de Grafos — Matemática Discreta UAB 12 IDEAS CLAVE El grafo completo contiene todas las aristas posibles entre sus vértices, sumando aristas.

El grafo nulo contiene vértices aislados y 0 aristas. El grafo rueda se genera acoplando un vértice central al ciclo , por lo que tiene orden y aristas. El hipercubo tiene vértices correspondientes a cadenas binarias y aristas entre cadenas con distancia de Hamming 1. En un grafo bipartito no existen aristas dentro del mismo subconjunto de la partición; los hipercubos son siempre bipartitos y coincide con . Las redes de área local emplean para topologías en estrella, para anillos y para esquemas híbridos redundantes. COMPRUEBA LO QUE HAS APRENDIDO 12. ¿Por qué el hipercubo Q es un grafo bipartito? 13. ¿En qué se diferencia el número de aristas de un grafo rueda W respecto al ciclo base C ?

FUNDAMENTOS DE GRAFOS 3 Representación matricial y subgrafos AL ACABAR SABRÁS Construir e interpretar las matrices de adyacencia y de incidencia de un grafo simple. Distinguir de forma rigurosa un subgrafo general de un subgrafo generador y de un subgrafo inducido. Efectuar correctamente las operaciones de eliminación de vértices y aristas evitando aristas huérfanas. Obtener el grafo complementario relativo al grafo completo correspondiente. PIÉNSALO ANTES DE LEER 14 ¿Qué ocurre con las conexiones de un grafo cuando eliminas un único vértice frente a cuando eliminas una única arista?

Representación matricial de grafos Para manipular grafos mediante algoritmos computacionales se requieren estructuras tabulares rigurosas. Las dos formas canónicas de representación matricial son la matriz de adyacencia y la matriz de incidencia. K n n 2 n(n 1) N n n W n C n n + 1 2n Q n 2n Q n Q 2 K 2,2 K 1,n C n W n Apuntes de Teoría de Grafos — Matemática Discreta UAB 13 DEFINICIÓN Sea un grafo simple de orden con conjunto de vértices . La matriz de adyacencia de , denotada por , es una matriz cuadrada de dimensión definida por: Esta matriz presenta tres propiedades fundamentales en grafos simples: Simetría: Al ser aristas no dirigidas, es idéntica a , lo que implica que para todo .

Por lo tanto, es una matriz simétrica respecto a su diagonal principal. Ceros en la diagonal principal: Dado que un grafo simple carece de bucles (véase «Fundamentos de grafos — Conceptos básicos y tipos de grafos»), ningún vértice es adyacente a sí mismo, de modo que para todo . Grado del vértice: La suma de los elementos de cualquier fila (o columna ) equivale al número de aristas que conectan a , es decir, su grado: (véase «Fundamentos de grafos — Grados de vértices e isomorfismo»). Por otro lado, la matriz de incidencia codifica la relación existente entre los vértices y las aristas del grafo. DEFINICIÓN Sea un grafo simple con vértices y aristas .

La matriz de incidencia de , denotada por , es una matriz rectangular de tamaño definida por: En la matriz de incidencia se distinguen dos propiedades estructurales directas: Suma de cada columna: En un grafo simple, cada arista une exactamente dos extremos distintos. Por ello, cada columna contiene exactamente dos unos y el resto ceros: para toda columna . Suma de cada fila: El número de unos en la fila indica cuántas aristas inciden en , lo que equivale de nuevo a su grado: .

Característica Matriz de adyacencia Matriz de incidencia Dimensión (cuadrada) (rectangular) Relación representada Vértice – Vértice Vértice – Arista Diagonal principal Compuesta íntegramente por ceros No aplica (no es cuadrada en general) G = (V , E) n V = {v , v , … , v } 1 2 n G A(G) = [a ] ij n × n a = ij { 1 0 si {v , v } E i j en caso contrario {v , v } i j {v , v } j i a = ij a ji i, j A(G) a = ii 0 i = 1, … , n i i v i a = j=1 n ij deg(v ) i G = (V , E) V = {v , v , … , v } 1 2 n E = {e , e , …

, e } 1 2 m G I(G) = [m ] ij n × m m = ij { 1 0 si la arista e es incidente con el v rtice v j e ˊ i en caso contrario m = i=1 n ij 2 j i v i m = j=1 m ij deg(v ) i A(G) I(G) n × n n × m Apuntes de Teoría de Grafos — Matemática Discreta UAB 14 Característica Matriz de adyacencia Matriz de incidencia Suma de la fila Grado del vértice Grado del vértice Suma de la columna Grado del vértice Exactamente 2 (los dos extremos de ) COMPRUEBA 15 ¿Por qué la suma de cualquier columna en la matriz de incidencia de un grafo simple es siempre igual a 2?

Concepto general de subgrafo y variantes A partir de un grafo conocido se pueden aislar porciones estructurales conservando la coherencia entre vértices y aristas. DEFINICIÓN Un grafo es un subgrafo de si su conjunto de vértices y su conjunto de aristas están contenidos en los de : y . Dentro de los subgrafos existen dos tipos fundamentales según el criterio de selección aplicado: Subgrafo generador: Un subgrafo es un subgrafo generador de si conserva todos los vértices originales, es decir, . Se obtiene únicamente descartando aristas. Dado un grafo con aristas, existen exactamente 2^m subgrafos generadores distintos, pues cada arista puede incluirse o excluirse de forma independiente.

Subgrafo inducido: Dado un subconjunto no vacío , el subgrafo inducido por , denotado por , es aquel cuyo conjunto de vértices es y cuyo conjunto de aristas contiene todas las aristas de cuyos dos extremos pertenezcan a . No se puede omitir ninguna arista que conecte a elementos de .

ESQUEMA Jerarquía de tipos de subgrafos Tipo de subgrafo Condición sobre vértices Condición sobre aristas Subgrafo general (cualquier subconjunto válido) A(G) I(G) i deg(v ) i deg(v ) i j deg(v ) j e j H = (V (H), E(H)) G = (V (G), E(G)) G V (H) V (G) E(H) E(G) H G V (H) = V (G) G m U V U U U G U U Subgrafo general V(H) y E(H) contenidos en G Subgrafo generador Conserva todos los vértices: V(H)=V(G) Subgrafo G - e Elimina una única arista e Subgrafo inducido Conserva todas las aristas entre U Subgrafo G - v Inducido por V(G) sin el vértice v V (H) V (G) E(H) E(G) Apuntes de Teoría de Grafos — Matemática Discreta UAB 15 Tipo de subgrafo Condición sobre vértices Condición sobre aristas Subgrafo generador Subgrafo inducido Todas las aristas de con ambos extremos en COMPRUEBA 16 Si un grafo simple posee 4 aristas, ¿cuántos subgrafos generadores distintos se pueden construir a partir de él?

Operaciones de eliminación de elementos y grafo complementario Las operaciones básicas de supresión permiten generar subgrafos concretos retirando un único elemento de la estructura: Eliminación de un vértice ( ): Sea . El subgrafo tiene como vértices . Su conjunto de aristas contiene todas las aristas de excepto aquellas que inciden en . Formalmente, G - v es el subgrafo inducido por . Eliminación de una arista ( ): Sea . El subgrafo mantiene intacto el conjunto de vértices, , y su conjunto de aristas es . Por consiguiente, G - e es un subgrafo generador de .

ERROR FRECUENTE Al calcular , un fallo muy común en los exámenes es borrar únicamente el vértice y mantener aristas que tenían a como extremo. Una arista no puede existir sin sus dos vértices incidentes: al suprimir un vértice es obligatorio eliminar automáticamente todas las aristas conectadas a él. En contraste, en se retira la arista pero sus dos vértices extremos permanecen en el grafo. A partir del concepto de subgrafo generador respecto a un grafo completo de igual orden se formula el complementario de una red. DEFINICIÓN Sea un grafo simple de orden .

El grafo complementario de , denotado por , es el subgrafo del grafo completo que contiene a los vértices de y todas las aristas de que no pertenecen a . De esta definición se deducen dos propiedades inmediatas para grafos simples: V (H) = V (G) E(H) E(G) U V (H) = U V (G) G U G v v V (G) G v V (G v) = V (G) {v} E(G v) G v V (G) {v} G e e E(G) G e V (G e) = V (G) E(G e) = E(G) {e} G G v v v G e G = (V , E) n G G K n n G K n G Dos vértices distintos son adyacentes en si y solo si no son adyacentes en . 1 G G Dado que el grafo completo posee aristas en total, la suma de los tamaños de un grafo y de su complementario satisface la relación cardinal: .

2 K n 2 n(n 1) E(G) + E( ) = G 2 n(n 1) Apuntes de Teoría de Grafos — Matemática Discreta UAB 16 COMPRUEBA 17 ¿Cuál es la relación estructural entre G - v y G - e en términos de tipos de subgrafo? IDEAS CLAVE La matriz de adyacencia de un grafo simple es simétrica, tiene ceros en la diagonal y la suma de su fila es . La matriz de incidencia tiene dimensión , la suma de cada columna es exactamente 2 y la suma de cada fila es el grado del vértice correspondiente. Un subgrafo generador mantiene exactamente el mismo conjunto de vértices que el grafo original; un grafo con aristas posee subgrafos generadores.

Un subgrafo inducido incluye obligatoriamente todas las aristas originales cuyos dos extremos pertenecen al subconjunto de vértices . Eliminar un vértice produce el subgrafo inducido suprimiendo todas sus aristas incidentes, mientras que eliminar una arista produce el subgrafo generador . El grafo complementario reúne todas las aristas del grafo completo que no están presentes en . COMPRUEBA LO QUE HAS APRENDIDO 18. ¿Qué dimensión tienen la matriz de adyacencia y la matriz de incidencia de un grafo simple de orden 5 y tamaño 7? 19. ¿Por qué la diagonal principal de la matriz de adyacencia de un grafo simple contiene exclusivamente ceros? 20.

Si un grafo simple tiene orden 4 y cuenta con 2 aristas, ¿cuántas aristas contiene su complementario? FUNDAMENTOS DE GRAFOS 4 Grados de vértices e isomorfismo AL ACABAR SABRÁS Aplicar el lema del apretón de manos para relacionar el número de aristas y los grados de los vértices. Demostrar formalmente que el número de vértices de grado impar es siempre par. Evaluar invariantes estructurales para descartar o plantear el isomorfismo entre dos grafos. i deg(v ) i n × m m 2m U U G v G e G K n G Apuntes de Teoría de Grafos — Matemática Discreta UAB 17 PIÉNSALO ANTES DE LEER 21 ¿Es posible que en una reunión de 7 personas cada una salude de mano exactamente a otras 3 personas?

Grado de un vértice y propiedades fundamentales El comportamiento local de una red depende de cuántas conexiones inciden en cada nodo. Para un grafo no dirigido (véase «Fundamentos de grafos — Conceptos básicos y tipos de grafos»), el grado de un vértice , denotado por o , representa el número total de aristas que inciden en él. DEFINICIÓN: GRADO DE UN VÉRTICE Dado un grafo no dirigido , el grado de un vértice equivale a la cantidad de aristas incidentes en . En el caso de que la estructura admita bucles (como ocurre en los pseudógrafos), cada bucle aporta exactamente 2 unidades al cómputo del grado del vértice donde se apoya, ya que la arista sale y regresa al mismo nodo.

A partir del grado de cada vértice individual, surge una relación directa con el tamaño global del grafo (su número de aristas ). El lema del apretón de manos Cuando sumamos los grados de todos los elementos de , contabilizamos los extremos de todas las aristas presentes en la estructura. TEOREMA: LEMA DEL APRETÓN DE MANOS (SUMA DE GRADOS) Sea un grafo no dirigido con tamaño . Entonces: La demostración es inmediata: cada arista une dos extremos (o incide dos veces en el mismo nodo en caso de ser un bucle). Por tanto, cada arista contribuye exactamente en dos unidades a la suma global de los grados.

Una consecuencia fundamental de este lema es la restricción sobre la cantidad de vértices cuyos grados no son pares. COROLARIO DE PARIDAD En todo grafo no dirigido, el número de vértices de grado impar es par.

Para demostrarlo, dividimos el conjunto de vértices en dos subconjuntos disjuntos: , formado por los vértices de grado par, y , formado por los vértices de grado impar: G = (V , E) v deg(v) d(v) G = (V , E) deg(v) v V v m = E V G = (V , E) m = E deg(v) = v V 2m V V 1 V 2 2m = deg(v) = v V deg(v) + v V 1 deg(v) v V 2 Apuntes de Teoría de Grafos — Matemática Discreta UAB 18 Dado que es siempre par y la suma consta únicamente de sumandos pares (resultando en un valor par), la diferencia también debe ser par: Al ser cada término individual de este sumatorio un número impar, la única forma de que su total sea un número par es que contenga una cantidad par de términos.

Por ende, la cardinalidad es necesariamente par. COMPRUEBA 22 ¿Puede existir un grafo simple de 7 vértices donde cada vértice tenga exactamente grado 3? Grafos regulares Un caso de especial interés estructural ocurre cuando todos los vértices exhiben idéntica conectividad local. DEFINICIÓN: GRAFO K-REGULAR Un grafo se denomina regular si todos sus vértices tienen el mismo grado. Decimos que es k- regular si para todo . Si un grafo regular posee orden y tamaño , el lema del apretón de manos adopta la forma: EJEMPLO: GRAFO 4-REGULAR DE 10 ARISTAS ¿Es viable la existencia de un grafo 4-regular que posea aristas? Aplicando la igualdad fundamental: , por lo que , deduciendo vértices.

Un ejemplo concreto con estas características es el grafo completo (véase «Fundamentos de grafos — Familias especiales de grafos y topologías de red»), donde cada uno de los 5 vértices se conecta a los 4 restantes. Isomorfismo de grafos En el análisis de grafos, las etiquetas asignadas a los vértices o su disposición gráfica carecen de relevancia estructural intrínseca. Lo que define a un grafo es exclusivamente el patrón con el que sus vértices se conectan mediante aristas.

2m deg(v) v V 1 deg(v) = v V 2 2m deg(v) v V 1 0 (mod 2) V 2 deg(v) = k v V n = V m = E n k = 2m m = 2 n k m = 10 2(10) = 4 V 20 = 4 V V = 5 K 5 Apuntes de Teoría de Grafos — Matemática Discreta UAB 19 DEFINICIÓN: ISOMORFISMO DE GRAFOS Dos grafos y son isomorfos (denotado ) si existe una función biyectiva que preserva las adyacencias, satisfaciendo que: A la función biyectiva se la denomina isomorfismo. Si dos grafos son isomorfos, representan en el fondo la misma red, como ocurre al graficar el hipercubo de distintas maneras en el plano (véase «Fundamentos de grafos — Familias especiales de grafos y topologías de red»).

Determinar si dos grafos arbitrarios de orden son isomorfos mediante fuerza bruta exige examinar biyecciones posibles, lo que resulta computacionalmente inviable conforme crece. Invariantes de isomorfismo y protocolo de descarte Un invariante de isomorfismo es una propiedad estructural que se preserva bajo cualquier aplicación biyectiva admisible. Si dos grafos difieren en al menos un invariante, no pueden ser isomorfos.

Los tres invariantes primarios inmediatos son: PROCESO Protocolo para descartar isomorfismo 1 Comparar orden Verificar si "V1" = "V2" 2 Comparar tamaño Verificar si "E1" = "E2" 3 Secuencia de grados Comprobar idénticos multiconjuntos ordenados 4 Búsqueda de biyección Hallar f que preserve adyacencias Invariante evaluado Condición requerida para ser isomorfos Conclusión si no coincide Orden ("V") No son isomorfos Tamaño ("E") No son isomorfos Secuencia de grados Mismo multiconjunto de grados en orden No son isomorfos G = 1 (V , E ) 1 1 G = 2 (V , E ) 2 2 G 1 G 2 f : V 1 V 2 {u, v} E 1 {f(u), f(v)} E 2 f Q 3 n n!

n Mismo orden: Deben poseer idéntico número de vértices ( ), debido a la existencia de la biyección . 1 V = 1 V 2 f Mismo tamaño: Deben poseer idéntico número de aristas ( ), pues la biyección conserva adyacencias y no adyacencias. 2 E = 1 E 2 Misma secuencia de grados: Si tiene grado , su imagen debe tener necesariamente grado . La lista ordenada de los grados de todos sus vértices debe coincidir exactamente. 3 v V 1 d f(v) V 2 d V = 1 V 2 E = 1 E 2 Apuntes de Teoría de Grafos — Matemática Discreta UAB 20 EJEMPLO: DESCARTE POR SECUENCIAS DE GRADOS Sean dos grafos y , ambos con 6 vértices y 9 aristas. Supongamos que posee la secuencia de grados , mientras que tiene la secuencia .

Pese a coincidir en número de vértices y aristas, las secuencias de grado difieren (por ejemplo, tiene vértices de grado 3 y no), por lo que resulta imposible definir una biyección que preserve las adyacencias. Concluimos que no son isomorfos. ERROR FRECUENTE Asumir que si dos grafos comparten el orden, el tamaño y la secuencia de grados, entonces ya son automáticamente isomorfos. Estas condiciones son necesarias, pero NO suficientes. Dos grafos pueden tener la misma secuencia de grados (por ejemplo, ambos ser 3-regulares con 6 vértices) y poseer estructuras de conexiones internas incompatibles (como ciclos o subgrafos inducidos no equivalentes).

COMPRUEBA 23 Si dos grafos tienen el mismo orden y la misma secuencia de grados, ¿podemos asegurar que son isomorfos? IDEAS CLAVE Cada bucle aporta exactamente 2 unidades al grado del vértice donde reside. El lema del apretón de manos establece que la suma de todos los grados equivale al doble del número de aristas: . Todo grafo no dirigido contiene necesariamente una cantidad par de vértices con grado impar. En un grafo -regular se cumple la igualdad de conteo . El isomorfismo es una biyección de vértices que conserva adyacencias; las invariantes compartidas son condición necesaria pero no suficiente. COMPRUEBA LO QUE HAS APRENDIDO 24.

¿Por qué la suma de las filas de una matriz de adyacencia de un grafo simple coincide con el grado de cada vértice? 25. ¿Cuántas aristas posee un grafo 3-regular con 8 vértices? G 1 G 2 G 1 {2, 2, 3, 3, 4, 4} G 2 {2, 2, 2, 4, 4, 4} G 1 G 2 deg(v) = v V 2m k n k = 2m Apuntes de Teoría de Grafos — Matemática Discreta UAB 21 Test Rodea la respuesta correcta. Las soluciones están al final. 26. ¿Qué propiedad distingue de forma exclusiva a un pseudografo frente a un multigrafo? 27. ¿Cómo se define el tamaño de un grafo simple G = (V, E)? 28. En un digrafo, ¿cuál es la naturaleza matemática de cada arco? 29. Al modelar el tráfico de una ciudad, ¿cómo se representa una calle de sentido único? 30.

¿Cuántas aristas tiene el grafo completo K ? 31. ¿Cuál es el orden del grafo rueda W ? 32. ¿Qué grafo modela una red local con topología en estrella? 33. ¿A qué grafo bipartito completo es equivalente el hipercubo Q ? 34. ¿Qué representa la suma de los elementos de la fila i en la matriz de adyacencia de un grafo simple? 35. ¿Cuál es siempre la suma de cualquier columna en la matriz de incidencia de un grafo simple?

El orden finito de vértices a) La presencia de aristas dirigidas b) La existencia de bucles c) La asignación de pesos positivos d) El cardinal de vértices "V" a) El cardinal de aristas "E" b) La suma de aristas y vértices c) El número de componentes conectadas d) Una función biyectiva entre vértices a) Un número real no negativo b) Un par ordenado de vértices c) Un conjunto de cardinal dos d) Mediante un bucle reflexivo a) Mediante una arista con peso cero b) Mediante un arco dirigido c) Mediante una arista no dirigida d) 15 a) 30 b) 12 c) 6 d) 5 a) 11 b) 10 c) 6 d) a) C n b) K 1,n c) K n d) W n a) K 1,2 b) K 2,4 c) K 2,2 d) K 4,4 El grado del vértice vi a) El orden total del grafo b) El número total de aristas c) El doble del grado de vi d) El orden del grafo a) El grado del vértice b) Siempre 1 c) Siempre 2 d) Apuntes de Teoría de Grafos — Matemática Discreta UAB 22 36.

¿Qué condición define a un subgrafo generador H de un grafo G? 37. ¿Qué tipo de subgrafo se obtiene al suprimir un vértice v mediante la operación G - v? 38. ¿Cuál es la contribución de un bucle al grado de su vértice incidente? 39. En un grafo de 9 vértices, ¿es posible que todos tengan grado 3? 40. Si dos grafos tienen el mismo orden, tamaño y secuencia de grados, podemos concluir que: 41. Un grafo 4-regular tiene 6 vértices. ¿Cuántas aristas contiene?

Ser un grafo completo Kn a) Tener el mismo conjunto de aristas b) No contener aristas incidentes c) Tener el mismo conjunto de vértices d) Un grafo regular a) El grafo complementario b) Un subgrafo inducido c) Un subgrafo generador d) Aporta 0 al grado a) Aporta 2 al grado b) Aporta 4 al grado c) Aporta 1 al grado d) Sí, si es regular a) No, faltan vértices pares b) No, violaría la paridad c) Sí, si tiene ciclos d) Tienen las mismas etiquetas a) Son siempre isomorfos b) No pueden ser isomorfos c) Podrían no ser isomorfos d) 12 aristas a) 24 aristas b) 10 aristas c) 8 aristas d) Apuntes de Teoría de Grafos — Matemática Discreta UAB 23 5 Recorridos, distancias y componentes conexas AL ACABAR SABRÁS Clasificar secuencias de vértices y aristas en recorridos, cadenas, caminos, circuitos y ciclos Calcular distancias y el diámetro D(G) en un grafo no dirigido Determinar las componentes conexas w(G) y justificar la conexión mediante relaciones de equivalencia PIÉNSALO ANTES DE LEER 42 ¿Por qué el camino más corto entre dos vértices nunca repite ningún vértice intermedio?

El análisis de rutas de comunicación y transporte mediante grafos requiere formalizar el desplazamiento a través de sus elementos. En esta sección abordamos la estructura secuencial del movimiento en grafos no dirigidos y los conceptos métricos fundamentales de conexión.

ESQUEMA Estructura del tema: Caminos y Conexión Conectividad en grafos 5 Recorridos, distancias y componentes conexas 6 Aristo-conectividad y vértice- conectividad Secuencias en grafos Recorridos, cadenas y caminos Recorridos abiertos Cadenas y caminos simples Recorridos cerrados Circuitos y ciclos Métrica en grafos Distancia mínima y diámetro Conectividad Conexión, clases y componentes w(G) Apuntes de Teoría de Grafos — Matemática Discreta UAB 24 Secuencias de vértices y aristas: recorridos Sea un grafo no dirigido y dos vértices , no necesariamente distintos. Un recorrido de a (o recorrido) consiste en una secuencia alternada de vértices y aristas: donde cada arista para todo .

El vértice inicial es y el vértice final es . DEFINICIÓN La longitud de un recorrido es el número total de aristas que lo componen. Si una arista se atraviesa varias veces, se contabiliza tantas veces como aparezca. Un recorrido puede especificarse citando únicamente la secuencia ordenada de aristas o bien la secuencia de vértices cuando no exista ambigüedad. Decimos que un recorrido es cerrado cuando el origen y el destino coinciden ( ) y su longitud es estrictamente mayor que cero ( ). En caso contrario, si los extremos son distintos, se denomina abierto.

Taxonomía estricta de recorridos abiertos y cerrados Según las restricciones impuestas sobre la repetición de aristas o vértices, se define una jerarquía rigurosa de secuencias: Cadena: es un recorrido que no repite aristas. Puede repetir vértices intermedios. Camino: es un recorrido que no repite vértices internos. Al no repetir vértices, tampoco repite aristas. Circuito: es una cadena cerrada, es decir, un recorrido cerrado que no repite ninguna arista. Ciclo: es un camino cerrado, es decir, un recorrido cerrado sin repetición de vértices, salvo el inicial y final. Tipo de secuencia Extremos ¿Repite aristas? ¿Repite vértices internos?

Recorrido abierto Permitido Permitido Cadena No Permitido Camino No No Recorrido cerrado ( ) Permitido Permitido Circuito ( ) No Permitido Ciclo ( ) No No G = (V , E) x, y V x y x y x = x , e , x , e , x , … , e , x , e , x = 0 1 1 2 2 n 1 n 1 n n y e = i {x , x } i 1 i E 1 i n x y n x = y n > 1 x = y x = y x = y x = y n > 1 x = y n > 1 x = y n > 1 Apuntes de Teoría de Grafos — Matemática Discreta UAB 25 EJEMPLO Consideremos los vértices etiquetados en una red: La secuencia de vértices representa un recorrido abierto donde se repite la arista y los vértices . La secuencia utiliza aristas distintas en cada paso pero repite los vértices y : se trata de una cadena de longitud 5.

La secuencia no repite ningún vértice: constituye un camino de longitud 3. La secuencia cerrada no repite aristas pero pasa dos veces por : es un circuito de longitud 7. La secuencia cerrada no repite vértices intermedios: es un ciclo de longitud 4. ERROR FRECUENTE Confundir cadena con camino. Toda cadena prohíbe repetir aristas pero sí permite cruzar el mismo vértice varias veces. En cambio, un camino prohíbe estrictamente la repetición de vértices. Por consiguiente, todo camino es automáticamente una cadena, pero no toda cadena es un camino. COMPRUEBA 43 ¿Puede un recorrido que repite aristas ser considerado una cadena?

Propiedades métricas: distancia y diámetro La conectividad entre pares de vértices permite definir nociones métricas basadas en la longitud de las secuencias que los unen. DEFINICIÓN Dados dos vértices de un grafo , la distancia se define como la longitud del camino más corto que une con . Si no existe ningún camino entre ambos vértices, se establece por convenio que . La función distancia satisface los axiomas de una métrica en el conjunto : a, b, c, d, b, c, f {b, c} b, c d, b, c, e, d, c b c a, b, c, f a, e, f, i, j, e, d, a e d, e, j, k, d x, y V G d(x, y) x y d(x, y) = + d : V × V R {+ } V No negatividad y separación: para todo par, y se cumple si y solo si .

La longitud mínima entre un vértice y sí mismo es cero. 1 d(x, y) 0 d(x, y) = 0 x = y Simetría: , dado que en un grafo no dirigido cualquier camino entre e puede recorrerse en orden inverso preservando su longitud. 2 d(x, y) = d(y, x) x y Desigualdad triangular: para cualquier terna de vértices , se verifica . Al concatenar el camino mínimo de a con el de a , se genera un recorrido de a cuya longitud es la suma de ambas distancias; la distancia mínima será menor o igual que dicha longitud.

3 x, y, v V d(x, y) d(x, v) + d(v, y) x v v y x y d(x, y) Apuntes de Teoría de Grafos — Matemática Discreta UAB 26 DEFINICIÓN El diámetro de un grafo , denotado por , es el máximo de las distancias mínimas entre todos los pares de vértices: Si el grafo contiene pares de vértices no comunicados, la distancia entre ellos es , lo que implica que el diámetro resulta infinito. COMPRUEBA 44 Si entre los vértices u y v existen caminos de longitudes 2, 4 y 5, ¿cuál es el valor de d(u, v)? Grafos conexos, relación de equivalencia y componentes Un grafo se denomina grafo conexo si y solo si existe al menos un camino entre cualquier par de vértices distintos de .

Cuando se retira una arista o un vértice (conceptos estudiados en «Fundamentos de grafos — Representación matricial y subgrafos»), un grafo conexo puede perder esta propiedad y fragmentarse. Diremos que dos vértices e están conectados en si existe un camino que une a con . Esta noción define una relación binaria sobre el conjunto de vértices , denotada por : Reflexiva: todo vértice está conectado consigo mismo mediante el camino trivial de longitud 0 ( ). Simétrica: si , existe un camino de a ; al invertir sus aristas se obtiene un camino de a , de modo que . Transitiva: si y , existen caminos entre ellos. Su unión contiene un camino simple entre e , probando que .

Al ser una relación de equivalencia, la conexión induce una partición de en clases de equivalencia disjuntas . DEFINICIÓN Los subgrafos inducidos por dichas clases de equivalencia, , se denominan componentes conexas de . El número total de componentes conexas de un grafo se denota formalmente por . A partir de esta definición se deduce directamente que un grafo es conexo si y solo si w(G) = 1. Si , el grafo es no conexo o disconexo, y no existe ningún camino entre vértices situados en componentes diferentes. COMPRUEBA 45 ¿Qué valor toma w(G) si un grafo contiene 4 vértices aislados sin aristas?

G = (V , E) D(G) D(G) = max{d(x, y) x, y V } + G = (V , E) V x y G x y V x y x x x x y x y y x y x x v v y x y x y V V , V , … , V 1 2 k V , V , … , V 1 2 k G w(G) G w(G) > 1 Apuntes de Teoría de Grafos — Matemática Discreta UAB 27 IDEAS CLAVE Un recorrido es una secuencia alternada de vértices y aristas cuya longitud es el total de aristas recorridas. Una cadena no repite aristas; un camino no repite vértices internos. Un circuito es una cadena cerrada y un ciclo es un camino cerrado. La distancia es la longitud del camino más corto y cumple las propiedades de métrica. El diámetro representa la máxima distancia mínima entre cualquier par de vértices del grafo.

La relación de conexión entre vértices es de equivalencia y particiona el grafo en componentes conexas, cumpliéndose si y solo si el grafo es conexo. COMPRUEBA LO QUE HAS APRENDIDO 46. ¿En qué se distingue formalmente un circuito de un ciclo? 47. ¿Por qué la distancia entre vértices satisface la desigualdad triangular ? 48. ¿Qué relación existe entre las clases de equivalencia de la relación 'estar conectados' y las componentes conexas? CONECTIVIDAD EN GRAFOS 6 Aristo-conectividad y vértice-conectividad AL ACABAR SABRÁS Caracterizar formalmente aristas puente y vértices de corte mediante ciclos y caminos. Calcular los parámetros de aristo-conectividad y vértice-conectividad en grafos conexos.

Demostrar y aplicar la desigualdad de Whitney κ(G) λ(G) δ(G). PIÉNSALO ANTES DE LEER 49 ¿Siempre cuesta menos esfuerzo desconectar una red eliminando nodos que eliminando enlaces? Robustez y vulnerabilidad en redes conexas Al modelar infraestructuras como sistemas de transporte o redes de datos, la conectividad básica no basta. Resulta crucial medir la resistencia estructural ante fallos: cuántos enlaces o nodos pueden fallar antes de aislar alguna parte del sistema.

Si denotamos por el número de componentes d(x, y) D(G) w(G) = 1 d(x, y) d(x, v) + d(v, y) w(G) Apuntes de Teoría de Grafos — Matemática Discreta UAB 28 conexas de un grafo (véase «Conectividad en grafos — Recorridos, distancias y componentes conexas»), un grafo conexo satisface . Cuando retiramos elementos, buscamos cuantificar si dicha cantidad aumenta. Aristas puente y aristo-conectividad DEFINICIÓN Una arista puente (o puente) es una arista cuya eliminación desconecta el grafo, cumpliendo . La presencia de un puente revela un punto débil directo en la red.

El siguiente teorema caracteriza con precisión geométrica cuándo un enlace actúa como puente: TEOREMA DE CARACTERIZACIÓN DE ARISTAS PUENTE Sea un grafo conexo y una arista de . Entonces, e es una arista puente si y solo si no pertenece a ningún ciclo en . Demostración: DEFINICIÓN La aristo-conectividad de un grafo conexo , denotada por , es el número mínimo de aristas cuya eliminación hace que el grafo resulte desconexo. Si un grafo conexo contiene al menos un puente, entonces su aristo-conectividad es directamente . Si se requieren al menos dos aristas para desconectarlo, se tiene . COMPRUEBA 50 ¿Puede una arista contenida en un triángulo ser una arista puente?

w(G) = 1 e E w(G e) > w(G) G e = {u, v} G G Implicación directa ( ): Supongamos por reducción al absurdo que es una arista puente y que forma parte de un ciclo . Por ser puente, , lo que significa que existen dos vértices desconectados en cuyo camino en cruzaba obligatoriamente por . Sin embargo, al estar en el ciclo , el resto del ciclo proporciona un camino alternativo entre y que no usa . En consecuencia, cualquier ruta que antes usara puede desviarse por dicho camino alternativo, manteniendo todos los vértices conectados en . Esto contradice que sea puente. 1 e = {u, v} C w(G e) > w(G) G e G e e C u v e e G e e Implicación recíproca ( ): Supongamos que no pertenece a ningún ciclo.

Si suponemos que no es puente, entonces , por lo que y continúan en la misma componente conexa en . Por tanto, existe un camino entre y en . Al añadir de nuevo la arista a dicho camino, se forma un ciclo en que contiene a , lo que contradice la hipótesis inicial. 2 e = {u, v} w(G e) = w(G) u v G e u v G e e G e G λ(G) λ(G) = 1 λ(G) = 2 Apuntes de Teoría de Grafos — Matemática Discreta UAB 29 Vértices de corte y vértice-conectividad Al suprimir un vértice, también se eliminan obligatoriamente todas las aristas que inciden en él (véase «Fundamentos de grafos — Representación matricial y subgrafos»).

DEFINICIÓN Un vértice de corte (o punto de articulación) es un vértice cuya supresión incrementa el número de componentes conexas del grafo, de modo que . El comportamiento de los caminos que atraviesan la red permite caracterizar estos vértices críticos: TEOREMA DE CARACTERIZACIÓN DE VÉRTICES DE CORTE Sea un grafo conexo. Un vértice es un vértice de corte si y solo si existen dos vértices distintos tales que pertenece a todo camino entre e en .

Demostración: DEFINICIÓN La vértice-conectividad (o simplemente conectividad) de un grafo conexo , denotada por , es el número mínimo de vértices que es preciso suprimir para que el grafo resultante sea desconexo o se convierta en el grafo trivial de un único vértice. COMPRUEBA 51 Si un grafo contiene un vértice de corte, ¿cuál es el valor de su vértice-conectividad κ(G)? La desigualdad de Whitney Existe una jerarquía natural entre la facilidad de desconectar un grafo mediante vértices, aristas o aislando un nodo de menor grado.

Si representamos por el grado mínimo entre todos los vértices de (véase «Fundamentos de grafos — Grados de vértices e isomorfismo»), esta relación queda descrita por el clásico teorema de Whitney. v V w(G v) > w(G) G v x, y = v v x y G Implicación directa ( ): Si es de corte, el subgrafo resultante posee componentes conexas inducidas . Tomando un vértice y otro , no existe ningún camino entre e en . Dado que sí era conexo y contenía caminos entre ellos, todos debían transitar necesariamente por el vértice eliminado . 1 v G v k 2 V , V , … , V 1 2 k x V 1 y V 2 x y G v G v Implicación recíproca ( ): Supongamos que todo camino entre e en atraviesa .

Al retirar , se destruyen todos los trayectos entre ambos nodos. En consecuencia, no puede existir un camino entre e en , lo que demuestra que es desconexo y, por tanto, es un vértice de corte.

2 x y G v v x y G v G v v G κ(G) δ(G) G Apuntes de Teoría de Grafos — Matemática Discreta UAB 30 TEOREMA DE WHITNEY Para todo grafo conexo , se cumple la doble desigualdad: Demostración de las dos cotas: PROCESO Cadena de cotas de la Desigualdad de Whitney 1 Vértice-conectivi dad κ(G) Mínimo número de vértices que desconectan el grafo 2 Aristo-conectivi dad λ(G) Mínimo número de aristas que desconectan el grafo 3 Grado mínimo δ(G) Aristas necesarias para aislar el vértice menos conectado Parámetro Notación Elemento eliminado Condición de corte mínimo Vértice- conectividad Vértices y sus aristas incidentes Desconecta o deja un único vértice Aristo-conectividad Únicamente aristas Desconecta en componentes Grado mínimo Aristas de un vértice extremo Aísla el nodo de menor incidencia ERROR FRECUENTE Asumir que y siempre coinciden.

Aunque en grafos muy simétricos pueden ser iguales, a menudo se da la desigualdad estricta . Por ejemplo, dos triángulos unidos únicamente por un vértice común tienen (ese vértice es de corte), pero (se necesitan cortar al menos dos aristas para separar el grafo). G = (V , E) κ(G) λ(G) δ(G) Cota superior ( ): Consideremos un vértice cuyo grado sea el mínimo del grafo, es decir, . Si eliminamos todas las aristas incidentes en , este queda completamente aislado del resto del grafo. Como el número de aristas retiradas es exactamente y esta acción desconecta a , el tamaño mínimo requerido para desconectar no puede exceder esta cantidad. Por tanto, .

1 λ(G) δ(G) v gr(v) = δ(G) v δ(G) v λ(G) λ(G) δ(G) Cota inferior ( ): Supongamos que tiene aristo-conectividad . Existe un conjunto de aristas cuya retirada divide el grafo en al menos dos componentes conexas disjuntas, llamémoslas y . Cada una de las aristas eliminadas conectaba un vértice de con uno de . Si en lugar de retirar las aristas seleccionamos un extremo de cada una de ellas, obtenemos a lo sumo vértices. Suprimiendo este conjunto de vértices, destruimos todas las conexiones entre ambas componentes (o reducimos el grafo al caso trivial). En consecuencia, el número mínimo de vértices necesarios para desconectar el grafo satisface .

2 κ(G) λ(G) G λ(G) λ(G) G 1 G 2 G 1 G 2 λ(G) κ(G) λ(G) κ(G) λ(G) 2 δ(G) κ(G) λ(G) κ(G) < λ(G) κ(G) = 1 λ(G) = 2 Apuntes de Teoría de Grafos — Matemática Discreta UAB 31 COMPRUEBA 52 ¿Qué valor toma la aristo-conectividad λ(G) si se sabe que δ(G) = 1 y el grafo es conexo? IDEAS CLAVE Una arista es puente si y solo si no forma parte de ningún ciclo del grafo. Un vértice es de corte si y solo si pertenece a todos los caminos entre algún par de nodos distintos. La aristo-conectividad indica el número mínimo de aristas a retirar para desconectar el grafo. La vértice-conectividad mide el número mínimo de vértices a eliminar para desconectar el grafo o dejar el grafo trivial.

El teorema de Whitney establece formalmente que para todo grafo conexo. COMPRUEBA LO QUE HAS APRENDIDO 53. En la desigualdad de Whitney, ¿por qué la aristo-conectividad nunca supera al grado mínimo? 54. ¿Cómo se prueba que una arista perteneciente a un ciclo no puede ser una arista puente? Test Rodea la respuesta correcta. Las soluciones están al final. 55. ¿Qué condición define a una cadena en un grafo? 56. ¿Qué es un ciclo en teoría de grafos? 57. ¿Cómo se define el diámetro D(G) de un grafo?

λ(G) κ(G) κ(G) λ(G) δ(G) Tener longitud mínima a) No repetir ningún vértice b) Tener extremos coincidentes c) No repetir ninguna arista d) Cualquier recorrido de longitud par a) Un recorrido cerrado sin aristas repetidas b) Un recorrido abierto sin aristas repetidas c) Un camino cerrado sin vértices repetidos d) Suma de todas las aristas a) Longitud del camino más largo existente b) Promedio de grados de los vértices c) Máximo de las distancias mínimas entre vértices d) Apuntes de Teoría de Grafos — Matemática Discreta UAB 32 58. ¿Cuál es el valor de w(G) para cualquier grafo conexo? 59. ¿Cuál es la condición necesaria y suficiente para que una arista sea un puente? 60.

¿Qué relación general describe el teorema de Whitney en grafos conexos? 61. Si eliminar un único vértice v desconecta un grafo, ¿qué se puede afirmar sobre v? 62. ¿Cómo se define formalmente la aristo-conectividad λ(G)?

El número de vértices a) Exactamente uno b) Cero c) El número de aristas d) Pertenecer a un ciclo de longitud impar a) Incidir en un vértice de grado uno b) No estar contenida en ningún ciclo c) Conectar dos vértices de corte d) κ(G) λ(G) δ(G) a) λ(G) κ(G) δ(G) b) δ(G) κ(G) λ(G) c) κ(G) = λ(G) = δ(G) d) Es un vértice de corte a) Forma parte de todas las aristas puente b) Tiene grado estrictamente igual a dos c) Es un vértice aislado d) Máximo número de aristas independientes a) Mínimo número de aristas en un ciclo b) Grado del vértice con menos aristas c) Mínimo de aristas para desconectar el grafo d) Apuntes de Teoría de Grafos — Matemática Discreta UAB 33 7 Circuitos eulerianos y algoritmo de Fleury AL ACABAR SABRÁS Modelar problemas de recorridos mediante multigrafos analizando la paridad de sus vértices Demostrar las condiciones necesarias y suficientes para la existencia de circuitos y cadenas de Euler Aplicar el algoritmo de Fleury paso a paso respetando la restricción sobre aristas puente PIÉNSALO ANTES DE LEER 63 ¿Por qué es imposible dibujar una figura de un solo trazo sin levantar el lápiz si tiene más de dos intersecciones con un número impar de líneas?

El problema histórico de los puentes de Königsberg Durante el siglo XVIII, la ciudad de Königsberg en Prusia Oriental (actual Kaliningrado) presentaba una disposición geográfica peculiar: el río Pregel dividía la urbe en cuatro zonas de tierra firme distintas, entre las cuales figuraba la isla de Kneiphof. Siete puentes comunicaban estas zonas terrestres entre sí. Entre los ciudadanos surgió el reto de planificar un recorrido a pie que cruzara cada puente exactamente una vez y finalizara regresando al punto de partida. En 1736, el matemático suizo Leonhard Euler analizó este desafío abstrayendo los detalles geográficos innecesarios.

Euler representó las cuatro regiones de tierra como vértices y los siete puentes como aristas que conectaban dichos vértices, originando así un multigrafo (véase «Fundamentos de grafos — Conceptos básicos y tipos de grafos»). La cuestión urbana se tradujo a una pregunta estructural: ¿existe en este multigrafo un recorrido cerrado que recorra todas las aristas sin repetir ninguna? COMPRUEBA 64 ¿Por qué el problema de Königsberg se modela con un multigrafo y no con un grafo simple?

Rutas en grafos 7 Circuitos eulerianos y algoritmo de Fleury 8 Ciclos hamiltonianos y condiciones de existencia Apuntes de Teoría de Grafos — Matemática Discreta UAB 34 Circuitos de Euler, cadenas de Euler y grafos eulerianos Para abordar formalmente este tipo de problemas, la teoría de grafos define conceptos precisos en función del uso de aristas: DEFINICIÓN Un circuito de Euler en un grafo es una cadena cerrada (véase «Conectividad en grafos — Recorridos, distancias y componentes conexas») que contiene todas las aristas del grafo sin repetir ninguna.

Una cadena de Euler (o cadena euleriana abierta) en es una cadena que contiene todas las aristas del grafo cuyos vértices inicial y final son distintos. Un grafo se denomina euleriano si contiene al menos un circuito de Euler. Conviene notar que un grafo que admite un circuito de Euler no posee una cadena euleriana abierta (puesto que el recorrido que cubre todas las aristas necesariamente empieza y termina en el mismo…