Artículos

5: Teoría de grafos - Matemáticas


Este mapa de texto aún está en construcción. Por favor perdónanos.


Teoría de grafos

Nuestros editores revisarán lo que ha enviado y determinarán si deben revisar el artículo.

Teoría de grafos, rama de las matemáticas que se ocupa de las redes de puntos conectados por líneas. La asignatura de teoría de grafos tuvo sus inicios en problemas matemáticos recreativos (ver juego de números), pero se ha convertido en un área importante de investigación matemática, con aplicaciones en química, investigación de operaciones, ciencias sociales e informática.

La historia de la teoría de grafos se remonta específicamente a 1735, cuando el matemático suizo Leonhard Euler resolvió el problema del puente de Königsberg. El problema del puente de Königsberg era un viejo rompecabezas sobre la posibilidad de encontrar un camino sobre cada uno de los siete puentes que atraviesan un río bifurcado que pasa por una isla, pero sin cruzar ningún puente dos veces. Euler argumentó que tal camino no existe. Su demostración solo incluía referencias a la disposición física de los puentes, pero esencialmente demostró el primer teorema de la teoría de grafos.

Como se usa en la teoría de grafos, el término grafico no se refiere a gráficos de datos, como gráficos de líneas o gráficos de barras. En cambio, se refiere a un conjunto de vértices (es decir, puntos o nodos) y de aristas (o líneas) que conectan los vértices. Cuando dos vértices cualesquiera están unidos por más de un borde, el gráfico se llama multigraph. Un gráfico sin bucles y con como máximo un borde entre dos vértices se denomina gráfico simple. A menos que se diga lo contrario, grafico se supone que se refiere a un gráfico simple. Cuando cada vértice está conectado por una arista a todos los demás vértices, la gráfica se llama gráfica completa. Cuando sea apropiado, se puede asignar una dirección a cada borde para producir lo que se conoce como gráfico dirigido o dígrafo.

Un número importante asociado a cada vértice es su grado, que se define como el número de aristas que entran o salen de él. Por tanto, un bucle contribuye 2 al grado de su vértice. Por ejemplo, los vértices del gráfico simple que se muestra en el diagrama tienen todos un grado de 2, mientras que los vértices del gráfico completo que se muestra son todos de grado 3. Conocer el número de vértices en un gráfico completo caracteriza su naturaleza esencial. Por esta razón, los gráficos completos se designan comúnmente Knorte, dónde norte se refiere al número de vértices, y todos los vértices de Knorte tener grado norte - 1. (Traducido a la terminología de la teoría de grafos moderna, el teorema de Euler sobre el problema del puente de Königsberg podría reformularse de la siguiente manera: si hay un camino a lo largo de los bordes de un multigrafo que atraviesa cada borde una vez y solo una vez, entonces existe como máximo dos vértices de grado impar, además, si la ruta comienza y termina en el mismo vértice, ningún vértice tendrá un grado impar).

Otro concepto importante en la teoría de grafos es la ruta, que es cualquier ruta a lo largo de los bordes de una gráfica. Una ruta puede seguir un solo borde directamente entre dos vértices, o puede seguir múltiples bordes a través de múltiples vértices. Si hay una ruta que une dos vértices cualesquiera en un gráfico, se dice que ese gráfico está conectado. Un camino que comienza y termina en el mismo vértice sin atravesar ningún borde más de una vez se llama circuito o camino cerrado. Un circuito que sigue cada borde exactamente una vez mientras visita cada vértice se conoce como circuito euleriano, y la gráfica se llama gráfica euleriana. Un grafo euleriano está conectado y, además, todos sus vértices tienen grado par.

En 1857, el matemático irlandés William Rowan Hamilton inventó un rompecabezas (el Icosian Game) que luego vendió a un fabricante de juegos por £ 25. El rompecabezas consistía en encontrar un tipo especial de camino, más tarde conocido como circuito hamiltoniano, a lo largo de los bordes de un dodecaedro (un sólido platónico que consta de 12 caras pentagonales) que comienza y termina en la misma esquina mientras pasa por cada esquina exactamente una vez. La gira del caballero (ver juego de números: problemas de tablero de ajedrez) es otro ejemplo de un problema recreativo que involucra un circuito hamiltoniano. Los gráficos hamiltonianos han sido más difíciles de caracterizar que los gráficos eulerianos, ya que aún se desconocen las condiciones necesarias y suficientes para la existencia de un circuito hamiltoniano en un gráfico conectado.

Las historias de la teoría de grafos y la topología están estrechamente relacionadas y las dos áreas comparten muchos problemas y técnicas comunes. Euler se refirió a su trabajo sobre el problema del puente de Königsberg como un ejemplo de geometria situs—La "geometría de la posición" - mientras que el desarrollo de las ideas topológicas durante la segunda mitad del siglo XIX se conoció como sitio de análisis—El “análisis de posición”. En 1750 Euler descubrió la fórmula poliédrica Vmi + F = 2 relacionando el número de vértices (V), bordes (mi) y caras (F) de un poliedro (un sólido, como el dodecaedro mencionado anteriormente, cuyas caras son polígonos). Los vértices y los bordes de un poliedro forman un gráfico en su superficie, y esta noción llevó a considerar gráficos en otras superficies como un toro (la superficie de una dona sólida) y cómo dividen la superficie en caras en forma de disco. La fórmula de Euler pronto se generalizó a las superficies como Vmi + F = 2 – 2gramo, dónde gramo denota el género, o el número de "agujeros de rosquilla", de la superficie (ver Característica de Euler). Habiendo considerado una superficie dividida en polígonos por un gráfico incrustado, los matemáticos comenzaron a estudiar formas de construir superficies, y luego espacios más generales, pegando polígonos juntos. Este fue el comienzo del campo de la topología combinatoria, que más tarde, a través del trabajo del matemático francés Henri Poincaré y otros, se convirtió en lo que se conoce como topología algebraica.

La conexión entre la teoría de grafos y la topología condujo a un subcampo llamado teoría de grafos topológica. Un problema importante en esta área se refiere a los gráficos planos. Estos son gráficos que se pueden dibujar como diagramas de puntos y líneas en un plano (o, de manera equivalente, en una esfera) sin ningún borde que se cruce excepto en los vértices donde se encuentran. Los gráficos completos con cuatro o menos vértices son planos, pero los gráficos completos con cinco vértices (K5) o más no lo son. Los gráficos no planos no se pueden dibujar en un plano o en la superficie de una esfera sin bordes que se crucen entre sí entre los vértices. El uso de diagramas de puntos y líneas para representar gráficos surgió en realidad de la química del siglo XIX, donde los vértices con letras denotaban átomos individuales y las líneas de conexión denotaban enlaces químicos (con el grado correspondiente a la valencia), en los que la planaridad tenía importantes consecuencias químicas. El primer uso, en este contexto, de la palabra grafico se atribuye al inglés James Sylvester del siglo XIX, uno de varios matemáticos interesados ​​en contar tipos especiales de diagramas que representan moléculas.

Otra clase de gráficos es la colección de gráficos bipartitos completos. Kmetro,norte, que constan de gráficos simples que se pueden dividir en dos conjuntos independientes de metro y norte vértices de tal manera que no hay aristas entre los vértices dentro de cada conjunto y cada vértice en un conjunto está conectado por una arista a cada vértice en el otro conjunto. Como K5, el gráfico bipartito K3,3 no es plano, refutando una afirmación hecha en 1913 por el problemático recreacional inglés Henry Dudeney sobre una solución al problema del “gas-agua-electricidad”. En 1930, el matemático polaco Kazimierz Kuratowski demostró que cualquier gráfico no plano debe contener un cierto tipo de copia de K5 o K3,3. Tiempo K5 y K3,3 no se pueden incrustar en una esfera, se pueden incrustar en un toro. El problema de la incrustación de gráficos se refiere a la determinación de superficies en las que se puede incrustar un gráfico y, por lo tanto, generaliza el problema de planaridad. No fue hasta finales de la década de 1960 que el problema de incrustación de los gráficos completos Knorte fue resuelto para todos norte.

Otro problema de la teoría de grafos topológicos es el problema de la coloración de mapas. Este problema es una consecuencia del conocido problema de los mapas de cuatro colores, que pregunta si los países en cada mapa se pueden colorear usando solo cuatro colores de tal manera que los países que comparten un borde tengan colores diferentes. Preguntado originalmente en la década de 1850 por Francis Guthrie, entonces estudiante de la University College London, este problema tiene una rica historia llena de intentos incorrectos de solución. En una forma teórica de grafos equivalente, uno puede traducir este problema para preguntar si los vértices de un grafo plano siempre se pueden colorear usando solo cuatro colores de tal manera que los vértices unidos por un borde tengan colores diferentes. El resultado fue finalmente probado en 1976 mediante la verificación computarizada de casi 2.000 configuraciones especiales. Curiosamente, el problema de coloración correspondiente con respecto al número de colores necesarios para colorear mapas en superficies de géneros superiores se resolvió por completo unos años antes, por ejemplo, los mapas en un toro pueden requerir hasta siete colores. Este trabajo confirmó que una fórmula del matemático inglés Percy Heawood de 1890 da correctamente estos números de coloración para todas las superficies excepto la superficie unilateral conocida como la botella de Klein, para la cual se determinó el número de coloración correcto en 1934.

Entre los intereses actuales de la teoría de grafos se encuentran los problemas relacionados con algoritmos eficientes para encontrar caminos óptimos (dependiendo de diferentes criterios) en grafos. Dos ejemplos bien conocidos son el problema del cartero chino (el camino más corto que visita cada borde al menos una vez), que se resolvió en la década de 1960, y el problema del viajante (el camino más corto que comienza y termina en el mismo vértice y visita cada uno de ellos). edge exactamente una vez), que sigue atrayendo la atención de muchos investigadores debido a sus aplicaciones en el enrutamiento de datos, productos y personas. El trabajo sobre tales problemas está relacionado con el campo de la programación lineal, que fue fundada a mediados del siglo XX por el matemático estadounidense George Dantzig.


2. Enlaces y sus estructuras

Una red de transporte posibilita los flujos de personas, mercancías o información, que se están produciendo a lo largo de sus enlaces. Por tanto, la teoría de grafos debe ofrecer la posibilidad de representar los movimientos como encadenamientos, que se pueden considerar en varios aspectos:

Conexión. Un conjunto de dos nodos ya que cada nodo está vinculado al otro. Considera si es posible un movimiento entre dos nodos, sea cual sea su dirección. Conocer las conexiones permite saber si es posible llegar a un nodo desde otro nodo dentro de un gráfico.

Camino. Una secuencia de enlaces que se recorren en la misma dirección. Para que exista una ruta entre dos nodos, debe ser posible viajar por una secuencia ininterrumpida de enlaces. Encontrar todas las rutas posibles en un gráfico es un atributo fundamental para medir la accesibilidad y los flujos de tráfico.

Cadena. Una secuencia de enlaces que tienen una conexión en común con el otro. La dirección no importa.

Longitud de un enlace, conexión o ruta. Se refiere a la etiqueta asociada a un enlace, una conexión o una ruta. Esta etiqueta puede ser la distancia, la cantidad de tráfico, la capacidad o cualquier atributo relevante de ese enlace. La longitud de una ruta es el número de enlaces (o conexiones) en esta ruta.

Ciclo. Se refiere a una cadena donde el nodo inicial y terminal es el mismo y que no usa el mismo enlace más de una vez es un ciclo.

Circuito. Una ruta donde corresponde el nodo inicial y terminal. Es un ciclo donde todos los enlaces se recorren en la misma dirección. Los circuitos son muy importantes en el transporte porque varios sistemas de distribución utilizan circuitos para cubrir tanto territorio como sea posible en una dirección (ruta de entrega).

Camarilla. Una camarilla es un subgrafo completo máximo donde todos los vértices están conectados.

Grupo. También llamada comunidad, se refiere a un grupo de nodos que tienen relaciones más densas entre sí que con el resto de la red. Se utiliza una amplia gama de métodos para revelar grupos en una red, en particular, se basan en medidas de modularidad (varianza intragrupo versus inter-grupo).

Red del ego. Para un nodo dado, la red del ego corresponde a un sub-gráfico donde solo se incluyen sus vecinos adyacentes y sus enlaces mutuos.

Región nodal. Una región nodal se refiere a un subgrupo (árbol) de nodos polarizados por un nodo independiente (cuyo enlace de flujo más grande conecta un nodo más pequeño) y varios nodos subordinados (cuyo enlace de flujo más grande conecta un nodo más grande). Se utilizan métodos de análisis de enlace único o múltiple para revelar tales regiones eliminando enlaces secundarios entre nodos y manteniendo solo los enlaces más pesados.

Gráfico dual. Un método de sintaxis espacial que considera los bordes como nodos y los nodos como bordes. En las redes de calles urbanas, las grandes avenidas formadas por varios segmentos se convierten en nodos únicos, mientras que las intersecciones con otras avenidas o calles se convierten en enlaces (bordes). Este método es particularmente útil para revelar estructuras jerárquicas en una red plana.

Vecino común. Para dos o más nodos, la cantidad de nodos a los que normalmente se conectan son dos.


B8.5 Teoría de grafos (2019-2020)

Los gráficos (redes abstractas) se encuentran entre las estructuras matemáticas más simples, pero sin embargo tienen una teoría estructural muy rica y bien desarrollada. Dado que los gráficos surgen naturalmente en muchos contextos dentro y fuera de las matemáticas, la teoría de gráficos es un área importante de las matemáticas y también tiene muchas aplicaciones en otros campos como la informática.

El objetivo principal del curso es presentar las ideas fundamentales de la teoría de grafos y algunas de las técnicas básicas de combinatoria.

El estudiante habrá desarrollado una comprensión básica de las propiedades de los gráficos y una apreciación de los métodos combinatorios utilizados para analizar estructuras discretas.

Introducción: definiciones básicas y ejemplos. Árboles y su caracterización. Euler recorre trayectos y ciclos largos. Coloración de vértices: teorema de Brooks, polinomio cromático. Coloración de bordes: teorema de Vizing. Gráficos planos, incluida la fórmula de Euler, gráficos duales. Teorema de flujo máximo - corte mínimo: aplicaciones que incluyen el teorema de Menger y el teorema de Hall. Teorema de Tutte sobre emparejamientos. Problemas extremos: teorema de Turan, problema de Zarankiewicz, teorema de Erd & # 337s-Stone.

Tenga en cuenta que las versiones de libros electrónicos de muchos libros en las listas de lectura se pueden encontrar en SOLO y ORLO.


5: Teoría de grafos - Matemáticas

Ahora volvemos al problema original de colorear gráficos: colorear mapas. Como se indica en la sección 1.1, el problema de colorear el mapa se puede convertir en un problema de colorear el gráfico. La figura 5.10.1 muestra el ejemplo de la sección 1.1.

Los gráficos formados a partir de mapas de esta manera tienen una propiedad importante: son planar.

Definición 5.10.1 Una gráfica $ G $ es plana si se puede representar mediante un dibujo en el plano de modo que no se crucen las aristas. $ cuadrado $

Tenga en cuenta que esta definición solo requiere que alguna representación del gráfico no tenga bordes cruzados. La figura 5.10.2 muestra dos representaciones de $ K_4 $ ya que en el segundo no se cruzan bordes, $ K_4 $ es plano.

El número de colores necesarios para colorear correctamente cualquier mapa es ahora el número de colores necesarios para colorear cualquier gráfico plano. Este problema se planteó por primera vez en el siglo XIX y rápidamente se conjeturaba que en todos los casos bastaba con cuatro colores. Esto se demostró finalmente en 1976 (véase la figura 5.10.3) con la ayuda de una computadora. En 1879, Alfred Kempe dio una prueba que era ampliamente conocida, pero que era incorrecta, aunque no fue hasta 1890 que Percy Heawood lo notó, quien modificó la prueba para mostrar que cinco colores son suficientes para colorear cualquier gráfico plano. Demostraremos este teorema de los cinco colores, pero primero necesitamos algunos otros resultados. Suponemos que todas las gráficas son simples.

Teorema 5.10.2 (Fórmula de Euler) Suponga que $ G $ es una gráfica plana conectada, dibujada de manera que no se crucen aristas, con $ n $ vértices y $ m $ aristas, y que la gráfica divide el plano en $ r $ regiones. Entonces $ r = m-n + 2. $

Prueba. La prueba es por inducción sobre el número de aristas. El caso base es $ m = n-1 $, el número mínimo de aristas en un gráfico conectado en $ n $ vértices. En este caso, $ G $ es un árbol y no contiene ciclos, por lo que el número de regiones es 1 y, de hecho, $ 1 = (n-1) -n + 2 $.

Ahora suponga que $ G $ tiene más de $ n-1 $ aristas, por lo que tiene un ciclo. Elimina un borde de un ciclo que forma $ G '$, que está conectado y tiene $ r-1 $ regiones, $ n $ vértices y $ m-1 $ bordes. Por la hipótesis de inducción $ r-1 = (m-1) -n + 2 $, que se convierte en $ r = m-n + 2 $ cuando sumamos 1 a cada lado. $ qed $

Lema 5.10.3 Suponga que $ G $ es un gráfico plano conectado simple, dibujado de manera que no se crucen bordes, con vértices $ n ge3 $ y bordes $ m $, y que el gráfico divide el plano en regiones $ r $. Entonces $ m le 3n-6 $.

Prueba. Sea $ f_i $ el número de aristas que colindan con el número de región $ i $ si la misma región está a ambos lados de una arista, esa arista se cuenta dos veces. Llamamos a los bordes contiguos a una región los bordes del límite de la región. Dado que $ G $ es simple y $ n ge3 $, cada región está delimitada por al menos 3 aristas. Entonces $ sum_^ r f_i = 2m $, ya que cada borde se cuenta dos veces, una vez para la región a cada lado del borde. De $ r = m-n + 2 $ obtenemos $ 3r = 3m-3n + 6 $, y como $ f_i ge 3 $, $ 3r le sum_^ r f_i = 2m $, entonces $ 3m-3n + 6 le 2m $, o $ m le 3n-6 $ como se desee. $ qed $

El teorema 5.10.4 $ K_5 $ no es plano.

Prueba. $ K_5 $ tiene 5 vértices y 10 aristas, y $ 10 not le 3 cdot 5-6 $, por lo que según el lema, $ K_5 $ no es plano. $ qed $

Lema 5.10.5 Si $ G $ es plano, entonces $ G $ tiene un vértice de grado como máximo 5.

Prueba. Podemos suponer que $ G $ está conectado (si no, trabaje con un componente conectado de $ G $). Suponga que $ d (v_i)> 5 $ para todo $ v_i $. Entonces $ 2m = sum_^ n d (v_i) ge 6n $. Por el lema 5.10.3, $ 3n-6 ge m $ entonces $ 6n-12 ge 2m $. Por tanto, $ 6n le 2m le 6n-12 $, una contradicción. $ qed $

Teorema 5.10.6 (Teorema de los cinco colores) Cada gráfico plano se puede colorear con 5 colores.

Prueba. La prueba es por inducción sobre el número de vértices $ n $ cuando $ n le 5 $ esto es trivial.

Ahora suponga que $ G $ es plano en más de 5 vértices según el lema 5.10.5 algún vértice $ v $ tiene un grado como máximo 5. Según la hipótesis de inducción, $ G-v $ se puede colorear con 5 colores. Colorea los vértices de $ G $, que no sean $ v $, ya que están coloreados en 5 colores de $ G-v $. Si $ d (v) le 4 $, entonces $ v $ se puede colorear con uno de los 5 colores para dar una coloración adecuada de $ G $ con 5 colores. Entonces ahora supongamos que $ d (v) = 5 $. Si los cinco vecinos de $ v $ están coloreados con cuatro o menos de los colores, entonces de nuevo $ v $ se puede colorear para dar una coloración adecuada de $ G $ con 5 colores.

Supongamos ahora que los cinco vecinos de $ v $ tienen un color diferente, como se indica en la figura 5.10.4.

Suponga que en $ G $ hay una ruta desde $ v_1 $ a $ v_3 $, y que los vértices a lo largo de esta ruta se colorean alternativamente de rojo y verde; llame a dicha ruta una ruta alterna rojo-verde. Luego, junto con $ v $, esta ruta forma un ciclo con $ v_2 $ en el interior y $ v_4 $ en el exterior, o viceversa. Esto significa que no puede haber una ruta alterna de color violeta-azul de $ v_2 $ a $ v_4 $. Suponiendo que $ v_2 $ está dentro del ciclo, cambiamos los colores de todos los vértices dentro del ciclo de color púrpura a azul, y todos los vértices azules se vuelven a colorear de color púrpura. Esta sigue siendo una coloración adecuada de todos los vértices de $ G $ excepto $ v $, y ahora ningún vecino de $ v $ es púrpura, por lo que al colorear $ v $ de color púrpura obtenemos una coloración adecuada de $ G $.

Si no hay una ruta alterna roja-verde de $ v_1 $ a $ v_3 $, entonces cambiamos el color de los vértices de la siguiente manera: Cambiamos el color de $ v_1 $ a verde. Cambie todos los vecinos verdes de $ v_1 $ a rojo. Continúe cambiando los colores de los vértices de rojo a verde o de verde a rojo hasta que no haya conflictos, es decir, hasta que se obtenga una nueva coloración adecuada. Debido a que no hay una ruta alterna entre rojo y verde de $ v_1 $ a $ v_3 $, el color de $ v_3 $ no cambiará. Ahora, ningún vecino de $ v $ está coloreado de rojo, por lo que al colorear $ v $ rojo obtenemos una coloración adecuada de $ G $. $ qed $


Temas a cubrir

Actualizada periódicamente. Cada tema durará entre 1 y 2 semanas. Eres responsable de tomar tus propias notas.

1. Conceptos básicos en teoría de grafos 1,5 semana.

Definiciones, trayectorias, ciclos y estelas, secuencias de grados, gráficos dirigidos, gráficos planos, ciclos de Hamilton y circuitos de Euler.

2. Árboles y algoritmos 2,5 semanas.

Teorema de Cayley, árboles de expansión y el algoritmo codicioso, DFS y BFS, árbol de expansión mínimo y rutas más cortas. Fórmulas de longitud de gancho para árboles binarios.

3. Coincidencias y factores 3 semanas.

Emparejamientos y cubiertas en gráfico bipartito, condición de emparejamiento de Hall y SDR, teoremas minmax de Konig, conjuntos independientes y conjuntos dominantes, emparejamiento de peso máximo y emparejamiento estable, algoritmos, teorema de 1 factor de Tutte.

4.Digráficos y flujos en red 2 semanas.

Dígrafos, el teorema de Ford-Fulkerson, el teorema de integralidad, oferta y demanda

5. Conectividad gráfica 1 semana.

Conectividad de vértice, conectividad de borde, teorema de Menger

6. Coloración de gráficos y teorema de Ramsey 2 semanas.

Teorema de Brook, teorema de Ramsey y números de Ramsey (Opcional: vista de la teoría de Ramsey, teorema de Van der Waerden, enunciado de densidad y principio de compacidad).

7. Teorema de Turan y teoría de grafos extremos 0,5 semana

8. Álgebra lineal en teoría de grafos 2 semanas

Espectral de gráficos, gráfico regular y lineal, teorema del árbol de matrices, secuencias de Brujin, ciclos y corte, polinomio de Tutte

9. Teorema de Dilworth y teoría de conjuntos extremos 1 semana

Conjuntos parcialmente ordenados, teorema de Dilworth, teorema de Erdos-Ko-Rada, Standard Young Tableaux, algoritmo RSK y teorema de Schensted.

Referencias principales

POLÍTICA DE RECUPERACIÓN: Solo se permitirá la recuperación de las pruebas y exámenes perdidos con una excusa por escrito aprobada por la universidad. Siempre que sea posible, los estudiantes deben informar al instructor antes de que se pierda un examen o prueba. De acuerdo con las Reglas para estudiantes universitarios, los estudiantes deben notificar a un instructor al final del siguiente día hábil después de faltar a un examen o prueba. De lo contrario, perderán sus derechos a un maquillaje.

POLÍTICA DE AUSENCIAS: Se espera la asistencia de forma regular. Si bien en ocasiones hay buenas razones para que elijas faltar a clase, mi experiencia ha sido que existe una fuerte correlación entre la asistencia (siempre que estés despierto y escuchando) y el rendimiento en el curso.

En caso de ausencia relacionada con una lesión o enfermedad, los estudiantes que se ausenten de la clase tres o más días deben proporcionar a los instructores la confirmación de un proveedor médico por una ausencia justificada.

DESHONESTIDAD ESCOLÁSTICA: Copiar trabajo realizado por otros, ya sea dentro o fuera de clase, es un acto de deshonestidad escolar y será procesado en la medida permitida por la política de la Universidad. La colaboración en las tareas, ya sea dentro o fuera de la clase, está prohibida a menos que su instructor le otorgue permiso para hacerlo. Para obtener más información sobre las políticas de la universidad con respecto a la deshonestidad escolar, consulte las Reglas para estudiantes universitarios.

POLÍTICA DE COPYRIGHT: Todos los materiales impresos difundidos en clase o en la web están protegidos por las leyes de derechos de autor. Se permite una copia Xerox (o descarga de la web) para uso personal. Está estrictamente prohibido realizar copias múltiples o la venta de cualquiera de estos materiales.

La Ley de Estadounidenses con Discapacidades (ADA) es un estatuto federal contra la discriminación que brinda protección integral a los derechos civiles de las personas con discapacidades. Entre otras cosas, esta legislación requiere que todos los estudiantes con discapacidades tengan garantizado un entorno de aprendizaje que proporcione ajustes razonables para sus discapacidades. Si cree que tiene una discapacidad que requiere una adaptación, comuníquese con los Servicios para personas con discapacidades, que actualmente se encuentran en el edificio de Servicios para personas con discapacidades en el complejo de Servicios para estudiantes en White Creek en el campus oeste o llame al 979-845-1637. Para obtener información adicional, visite http://disability.tamu.edu.

  • Las acusaciones de agresión sexual, discriminación sexual o acoso sexual cuando involucran a estudiantes, profesores o personal de TAMU, o terceros que visitan el campus.

Los estudiantes y el profesorado pueden informar sobre comportamientos que no sean de emergencia que les preocupen en Tell Somebody.


B8.5 Teoría de grafos - Material para el año 2020-2021

Los gráficos (redes abstractas) se encuentran entre las estructuras matemáticas más simples, pero sin embargo tienen una teoría estructural muy rica y bien desarrollada. Dado que los gráficos surgen naturalmente en muchos contextos dentro y fuera de las matemáticas, la teoría de gráficos es un área importante de las matemáticas y también tiene muchas aplicaciones en otros campos como la informática.

El objetivo principal del curso es presentar las ideas fundamentales de la teoría de grafos y algunas de las técnicas básicas de combinatoria.

El estudiante habrá desarrollado una comprensión básica de las propiedades de los gráficos y una apreciación de los métodos combinatorios utilizados para analizar estructuras discretas.

Introducción: definiciones básicas y ejemplos. Árboles y su caracterización. Euler recorre trayectos y ciclos largos. Coloración de vértices: teorema de Brooks, polinomio cromático. Coloración de bordes: teorema de Vizing. Gráficos planos, incluida la fórmula de Euler, gráficos duales. Teorema de flujo máximo - corte mínimo: aplicaciones que incluyen el teorema de Menger y el teorema de Hall. Teorema de Tutte sobre emparejamientos. Problemas extremos: teorema de Turan, problema de Zarankiewicz, teorema de Erd & # 337s-Stone.


Editores consultores

Jonathan L. Gross, Universidad de Columbia, Nueva York
Jonathan L. Gross es profesor de informática en la Universidad de Columbia. Su trabajo matemático en topología y teoría de grafos le ha valido una beca Alfred P. Sloan, una beca postdoctoral de IBM y numerosas becas de investigación. Con Thomas Tucker, escribió la teoría de gráficos topológicos y varios artículos pioneros fundamentales sobre gráficos de voltaje y métodos enumerativos. Ha escrito y editado ocho libros sobre teoría de grafos y combinatoria, siete libros sobre temas de programación informática y un libro sobre sociometría cultural.

Thomas W. Tucker, Universidad de Colgate, Nueva York
Thomas W.Tucker es profesor de matemáticas Charles Hetherington en la Universidad de Colgate, donde ha estado desde 1973, después de un doctorado en 3 variedades de Dartmouth en 1971 y un postdoctorado en Princeton (donde su padre AW Tucker fue presidente y la tesis de John Nash tutor). Es coautor (con Jonathan Gross) de Topological Graph Theory. Sus primeras publicaciones se centraron en 3 variedades no compactas, luego en teoría de grafos topológicos, pero su trabajo reciente es principalmente algebraico, especialmente en la distinción y la estructura teórica de grupos de mapas simétricos.


Conectividad perimetral

Sea "G" un gráfico conectado. El número mínimo de bordes cuya eliminación hace que "G" se desconecte se denomina conectividad de borde de G.

En otras palabras, el número de bordes en un conjunto de corte más pequeño de G se llama conectividad de borde de G.

Si 'G' tiene un borde cortado, entonces & lambda (G) es 1. (conectividad de borde de G.)

Eche un vistazo al siguiente gráfico. Al eliminar dos bordes mínimos, el gráfico conectado se desconecta. Por lo tanto, su conectividad de borde (& lambda (G)) es 2.

Aquí están las cuatro formas de desconectar el gráfico quitando dos bordes y menos


John Urschel

Soy un matemático aplicado. Mi investigación se centra en el análisis numérico, la teoría de grafos y la ciencia de datos / aprendizaje automático. Estoy principalmente interesado en resultados teóricos y garantías demostrables para algoritmos / problemas prácticos, que a menudo conducen a algoritmos nuevos y mejorados.

Actualmente soy un estudiante de doctorado de quinto año en matemáticas del MIT y tengo el placer de ser asesorado por Michel Goemans. Espero graduarme en la primavera de 2021.

Aquí hay algunas publicaciones seleccionadas:
1. Estimaciones de errores uniformes para el método Lanczos, preimpresión (2020) [PDF]
2. Con respecto a dos conjeturas sobre particiones clique y biclique, Preprint (2020) [PDF]
3. Sobre la caracterización y unicidad de las teselaciones de Voronoi centroidales, SINUM (2017) [PDF]
4. Aprendizaje de procesos de puntos determinantes con momentos y ciclos, ICML (2017) [PDF]
5. Bisección espectral de gráficos y conectividad, Lin Alg & App (2014) [PDF]

A continuación, puede encontrar una descripción detallada de mi investigación, una lista completa de mis publicaciones y mi enseñanza actual y pasada. Aquí hay un CV (probablemente desactualizado). Mis declaraciones de investigación y enseñanza están disponibles a pedido. Mi correo electrónico está arriba, aunque los correos electrónicos no académicos no recibirán respuesta.

Mi investigación consiste principalmente en temas de álgebra lineal numérica, teoría de grafos y ciencia de datos / aprendizaje automático, todos los cuales comparten una base en el álgebra lineal aplicada. A continuación se muestra una descripción de cada tema de investigación, así como una breve discusión de mis intereses particulares dentro de cada disciplina.

Álgebra lineal numérica: El campo del álgebra lineal numérica se ocupa fundamentalmente de la solución numérica de sistemas lineales Ax = by problemas de valores propios Ax = & lambdax. Estos cálculos tienen aplicaciones en ingeniería, ciencia y big data / aprendizaje automático, y el trabajo en esta área se centra en producir y analizar algoritmos que den como resultado una buena aproximación a una solución exacta con relativa rapidez. Mi investigación se centra principalmente en problemas de valores propios simétricos. Estoy particularmente interesado en algoritmos rápidos para calcular valores propios extremos, como los métodos del subespacio de Krylov, una técnica de reducción de dimensiones para resolver aproximadamente un sistema lineal o un problema de valores propios mediante el mapeo a un subespacio dimensional inferior bien elegido. Un área de aplicación de gran interés para mí es el cálculo de pares propios de baja energía de gráficos laplacianos. Los espacios propios de baja dimensión del laplaciano de un gráfico han demostrado ser útiles en varias áreas de la ciencia de datos, incluida la incrustación y la partición de gráficos.

Publicaciones de muestra:
1. Estimaciones de errores uniformes para el método Lanczos, preimpresión (2020) [PDF]
2. Un Alg. Multirrejilla Cascadica. para Comp. el vector de Fiedler de Graph Lapl., J. Comp. Matemáticas (2015) [PDF]
3. Un método de espacio-tiempo multirredes. para el Num. Val. de Opciones de Barrera, Com. en matemáticas. Aleta. (2013) [PDF]

Teoría de grafos: Los gráficos son estructuras que capturan relaciones por pares entre un conjunto discreto de objetos. Esta formulación abstracta hace que los gráficos sean útiles en una amplia variedad de contextos, dependiendo de la interpretación de una relación por pares. La mayor parte de mi investigación en esta área se centra en la teoría de grafos espectrales, el estudio de matrices asociadas con un grafo. La teoría de grafos espectrales ha demostrado su utilidad en varias aplicaciones. Por ejemplo, los valores propios extremos de la matriz de adyacencia o laplaciana se utilizan para la partición, la detección de comunidades, la reducción de dimensiones para grandes conjuntos de datos, la visualización de datos y una serie de otras tareas en la teoría de la ciencia de datos / aprendizaje automático. Estoy particularmente interesado en dominios nodales e incrustaciones de gráficos, entre una amplia gama de temas de investigación en el área.

Publicaciones de muestra:
1. Con respecto a dos conjeturas sobre particiones clique y biclique, Preprint (2020) [PDF]
2. Thms de seguimiento discreto. y Energía Mín. Spring Embed. of Planar Graphs, Lin Alg & App (2021) [PDF]
3. Bisección espectral de gráficos y conectividad, Lin Alg & App (2014) [PDF]

Ciencia de datos / Aprendizaje automático: La ciencia de datos es una amplia clase de técnicas y herramientas que se utilizan para extraer información útil de conjuntos de datos (a menudo grandes), y el campo relacionado del aprendizaje automático se ocupa de los algoritmos que mejoran a través de la experiencia (es decir, aumentos en los datos). Este tema es una de las áreas de investigación más populares e importantes del siglo XXI. Mis áreas de interés incluyen la agrupación en clústeres, la visualización de datos y los modelos probabilísticos para el aprendizaje automático. La agrupación en clústeres y la visualización de datos se superponen en gran medida con la teoría de grafos, pero también estudio varios enfoques que no tienen una formulación gráfica, como la cuantificación / k-medias. Una clase particularmente interesante de modelos probabilísticos son los procesos de puntos determinantes (DPP), una clase de modelos repulsivos que se originaron en la física cuántica y proporcionan una fuerte alternativa a los modelos gráficos. A DPP model captures negative correlation between a discrete set of objects, and has proven to be extremely useful in a number of applications, including the subset selection problem. The DPP model has an elegant linear algebraic formulation, as, given a set of n objects, the probability of a subset S appearing as a sample is proportional to the associated principal minor of some matrix. My research on DPPs mostly focuses on learning algorithms with proveable guarantees.

Sample Publications:
1. Maximum Likelihood Estimation of Determinantal Point Processes, Preprint (2020) [PDF]
2. On the Characterization and Uniqueness of Centroidal Voronoi Tessellations, SINUM (2017) [PDF]
3. Learning Determinantal Point Processes with Moments and Cycles, ICML (2017) [PDF]

Regarding Two Conjectures on Clique and Biclique Partitions

Uniform Error Estimates for the Lanczos Method

Maximum Likelihood Estimation of Determinantal Point Processes

Discrete Trace Theorems and Energy Minimizing Spring Embeddings of Planar Graphs


with Ludmil Zikatanov
Linear Algebra and its Applications, 2021. [PDF]

Testing Gap k-Planarity is NP-Complete


with Jake Wellens
Information Processing Letters, to appear. [PDF]

Nodal Decompositions of Graphs


Linear Algebra and its Applications, 2018. [PDF]

On the Characterization and Uniqueness of Centroidal Voronoi Tessellations


SIAM Journal on Numerical Analysis, 2017. [PDF]

Learning Determinantal Point Processes with Moments and Cycles


with Victor-Emmanuel Brunel, Ankur Moitra, and Philippe Rigollet
Proceedings of the 34th International Conference on Machine Learning (ICML 2017). [PDF]

Rates of Estimation for Determinantal Point Processes


with Victor-Emmanuel Brunel, Ankur Moitra, and Philippe Rigollet
Proceedings of the 30th Annual Conference on Learning Theory (COLT 2017). [PDF]

On the Approximation of Laplacian Eigenvalues in Graph Disaggregation

On the Maximal Error of Spectral Approximation of Graph Bisection

A Cascadic Multigrid Algorithm for Computing the Fiedler Vector of Graph Laplacians

Spectral Bisection of Graphs and Connectedness


with Ludmil Zikatanov
Linear Algebra and its Applications, 2014. [PDF]

A Space-Time Multigrid Method for the Numerical Valuation of Barrier Options


Communications in Mathematical Finance, 2013. [PDF]

Instabilities in the Sun-Jupiter-Asteroid Three Body Problem


with Joseph Galante
Celestial Mechanics and Dynamical Astronomy, 2013. [PDF]

Math 18.03: Differential Equations, MIT, Spring 2018
Role: Recitation Instructor
Subject Evaluation Report: 6.9/7 [PDF]

Math 232: Integral Vector Calculus, Penn State, Fall 2013
Role: Lecturer
Student Rating of Teaching Effectiveness: 6.71/7 [PDF]

Math 041: Trigonometry and Analytic Geometry, Penn State, Spring 2013
Role: Lecturer
Student Rating of Teaching Effectiveness: 6.59/7 [PDF]

© 2020 John C. Urschel -- template shamelessly stolen from Tselil Schramm.


Contributors

Jonathan L. Gross, Thomas W. Tucker, Lowell W. Beineke, Robin J. Wilson, Jianer Chen, Yuanqiu Huang, Bojan Mohar, R. Bruce Richter, Joan P. Hutchinson, G. Salazar, Tomaž Pisanski, Arjana Žitnik, Jin Ho Kwak, Jaeun Lee, Jozef Širáň, Arthur T. White, M. J. Grannell, T. S. Griggs, Mark E. Watkins, Dan Archdeacon

This title is available for institutional purchase via Cambridge Core

Cambridge Core offers access to academic eBooks from our world-renowned publishing programme.


Ver el vídeo: Teoría de grafos (Septiembre 2021).