Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 81 vistas

    Clase 1 Grafos

    Cargado por

    edmexia
    Este documento presenta un resumen de varios temas relacionados con grafos, incluyendo problemas históricos sobre puentes, el problema de los cuatro colores, definiciones básicas de grafos como conjuntos de vértices y aristas, representaciones como lista de adyacencia, teoremas sobre grados de vértices y cantidad de aristas, y conceptos como caminos, circuitos, grafos eulerianos y semieulerianos. Contiene también ejercicios para practicar estos conceptos.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Descargue como PDF, TXT o lea en línea desde Scribd

    Clase 1 Grafos

    Cargado por

    edmexia
    81 vistas36 páginas
    Este documento presenta un resumen de varios temas relacionados con grafos, incluyendo problemas históricos sobre puentes, el problema de los cuatro colores, definiciones básicas de grafos como conjuntos de vértices y aristas, representaciones como lista de adyacencia, teoremas sobre grados de vértices y cantidad de aristas, y conceptos como caminos, circuitos, grafos eulerianos y semieulerianos. Contiene también ejercicios para practicar estos conceptos.

    Título original

    Clase1Grafos

    Derechos de autor

    © Attribution Non-Commercial (BY-NC)

    Formatos disponibles

    PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Este documento presenta un resumen de varios temas relacionados con grafos, incluyendo problemas históricos sobre puentes, el problema de los cuatro colores, definiciones básicas de grafos como conjuntos de vértices y aristas, representaciones como lista de adyacencia, teoremas sobre grados de vértices y cantidad de aristas, y conceptos como caminos, circuitos, grafos eulerianos y semieulerianos. Contiene también ejercicios para practicar estos conceptos.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    81 vistas36 páginas

    Clase 1 Grafos

    Cargado por

    edmexia
    Este documento presenta un resumen de varios temas relacionados con grafos, incluyendo problemas históricos sobre puentes, el problema de los cuatro colores, definiciones básicas de grafos como conjuntos de vértices y aristas, representaciones como lista de adyacencia, teoremas sobre grados de vértices y cantidad de aristas, y conceptos como caminos, circuitos, grafos eulerianos y semieulerianos. Contiene también ejercicios para practicar estos conceptos.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    de 36

    Facultad de Ciencias e Ingeniera

    Carrera Profesional de Ingeniera de Sistemas e Informtica

    Matemticas Discretas Tema: Grafos Profesor: Pascual F. Onofre Mayta

    El problema de los sietes puentes


    Resea histrica: Los ciudadanos tomaban largas caminatas los domingos. Ellos se preguntaron si era posible iniciar en un sitio, cruzar por todos los puentes una sola vez, y regresar al punto de partida.

    El problema de los cuatros colores

    Red de cables

    Red de rea local

    Caminos ms corto

    Definicin de Grafo Es un conjunto no vaco de puntos (nodos o vrtices) y un conjunto de lneas (aristas o arcos) cada una de las cuales une un punto a otro.

    Grafo no dirigido

    Lista de adyacencia A: B ,C B:A,E,D C:A,E D:B,E,F E:B,C,D,F F:D,E

    Notacin para indicar un grafo: G = (V,E) V : Conjunto de vrtices |V| = Cantidad de vrtices E : Conjunto de aristas |E| = Cantidad de aristas

    Lista de adyacencia

    1:2,4 2:1,3,5 3:2,4 4:1,3,5 5:2,4

    Definiciones bsicas.
    1. Dos vrtices v1 y v2 en un grafo no dirigido son

    adyacentes, si el par no ordenado {v1,v2 } es una arista del grafo. 2. Si a = {v1,v2 }, decimos que la arista a incide en los vrtices v1 y v2 3. Grado de un vrtice: Es la cantidad de aristas incidentes al vrtice, y es denotado por gd(v).

    Teorema. En todo grafo no dirigido G = (V,E) , la suma de los grados de todos los vrtices del grafo es igual al doble del nmero de aristas del grafo
    Simblicamente,

    Ejemplo.

    gr(A) = 2 gr(B) = 3 gr(C) = 2 gr(D) = 3 gr(E) = 4 gr(F) = 2

    Cantidad de vrtices : 6 Cantidad de aristas : 8

    16

    El doble de nmero de aristas

    Ejemplo. Cuntos aristas tiene un grafo si los grados de sus vrtices son 4, 3, 3, 2, 2?. Dibuja un grafo que verifique con lo anterior Solucin.
    Usaremos la frmula,

    Entonces,

    Ejemplo. Cuntos vrtices se necesitan para obtener un grafo con 12 aristas y todos sus vrtices de grado 3? Solucin.
    En un grafo no dirigido , se cumple

    Se tiene que para todo entonces Como

    , se tiene que

    Ejercicio 1. Cuntas aristas hay en un grafo con diez vrtices, cada uno de los cules tiene grado seis? Solucin.
    La suma de los grados de todos los vrtices de un grafo no dirigido es el doble de la cantidad de aristas.

    Por lo tanto, 30 es la cantidad de aristas.

    Ejercicio 2. Se quiere establecer una red de conexiones entre los 15 ordenadores que hay en una empresa. Se puede conectar cada uno de estos ordenadores exactamente a otros 5 de ellos?

    Ejercicio 3. De cada ciudad de un pas, parten tres carreteras a otras tantas ciudades. Puede tener dicho pas un total de 100 carreteras?

    Ejercicio 4. En una huerta existen 8 canales que llevan el agua de una plantacin a otra. Entre dos plantaciones nunca existe ms de un canal. La tercera parte de las plantaciones es el extremo de dos canales y las restantes de tres. Cuntas plantaciones hay en dicha huerta? Demustralo formalmente. Solucin.
    Los canales representan las aristas y las plantaciones los vrtices para un grafo no dirigido. Sea la cantidad de vrtices. Segn el enunciado la tercera parte de vrtices tienen grado 2 y el resto tienen grado 3, donde obtenemos,

    Simplificando y despejando, obtenemos Un posible grafo es el siguiente

    Ejercicio 5. Determine la cantidad de vrtices y de aristas de un grafo cuya matriz de adyacencia es la siguiente

    Teorema. En todo grafo dirigido G = (V,E), la suma de los grados de salida y la suma de los grados de entrada coinciden con la cantidad de aristas del grafo.

    Ejercicio 6. Determine la cantidad de vrtices y de aristas de un grafo cuya matriz de adyacencia es la que se indica: (a) (b)

    Ejercicio 7. Imagine que el diagrama que se muestra a continuacin es un mapa con los pases de a a g. Determine si es posible colorear el mapa con slo tres colores de modo que no hay dos pases adyacentes que tengan el mismo color.

    Grafo dual

    Coloracin de grafos. Determinar el nmero cromtico de los siguientes grafos

    Ejercicio 8. Un departamento quiere programar exmenes finales as que ningn estudiante tiene ms de un examen en un da determinado. Los vrtices del grafo que se presenta a continuacin muestran los cursos que estn siendo tomados por ms de un estudiante, con una arista que conecta dos vrtices si hay un estudiante en ambos cursos. Encuentre una forma para colorear los vrtices del grafo con slo cuatro colores as que no hay dos vrtices adyacentes que tengan el mismo color y explique cmo utilizar el resultado para programar los exmenes finales

    a. b. c. d. e. f. g.

    MCS100 MCS101 MCS102 MCS135 MCS130 MCS110 MCS120

    Ejercicio 9. Cuntas aristas tiene un grafo si los grados de sus vrtices son 5, 2, 2, 2, 2, 1?. Dibuje un grafo que verifique lo anterior

    Ejercicio 10. Existe algn grafo simple de cinco vrtices con los grados siguientes?. Si es as, dibuja un grafo con esa propiedad. (a) 3, 3, 3, 3, 2 (d) 1, 1, 1, 1, 1 (b) 1, 2, 3, 4, 5 (e) 1, 2, 3, 4, 4 (c) 0, 1, 2, 2, 3

    Ejercicio 10. Existe algn grafo simple de cinco vrtices con los grados siguientes?. Si es as, dibuja un grafo con esa propiedad. (a) 3, 3, 3, 3, 2 (d) 1, 1, 1, 1, 1 (b) 1, 2, 3, 4, 5 (e) 1, 2, 3, 4, 4 (c) 0, 1, 2, 2, 3

    Definiciones bsicas
    Camino: Es una secuencia de aristas que comienza en un vrtice del grafo y recorre ciertas aristas del grafo siempre conectando pares de vrtices adyacentes. Circuito: Es un camino cuyo origen y final son el

    mismo vrtice. Circuito simple: Es un circuito cuyas aristas son todas distintas. Camino euleriano: Es un camino simple que contiene a todas las aristas del grafo. Circuito euleriano: Es un circuito simple que contiene a todas las aristas del grafo.

    Grafos eulerianos y semiulerianos Definicin. Se dice que un grafo no dirigido es conexo si dos vrtices cualesquiera se pueden unir mediante un camino. Si hay dos vrtices que no se pueden unir mediante un camino, se dice que el grafo es no conexo o disconexo. Teorema: Un multigrafo conexo contiene un circuito euleriano si, y slo si, cada uno de sus vrtices tienen grado par Teorema: Un multigrafo conexo contiene un camino euleriano, pero no un circuito euleriano si, y slo si, tiene exactamente dos vrtices de grado impar

    Ejemplos

    El algoritmo de Fleury permite determinar un circuito euleriano 1. Verificar que el grafo sea conexo y que todos los vrtices tengan grado par. Caso contrario el grafo no es euleriano y finalizar. 2. Si cumple con la condicin anterior, seleccionar un vrtice arbitrario para indicar el recorrido 3. Escoger una arista a partir del vrtice actual. Esa arista seleccionada no debe ser lado puente, a menos que no exista otra alternativa. // El lado puente es aquella arista que si se elimina,
    los grafos pierden la propiedad de ser conexos.

    4. Desconectar los vrtices que estn unidos por la arista seleccionada. 5. Si todos los vrtices del grafo ya estn desconectados, ya se tiene el circuito euleriano y finalizar. De otra manera continuar con el paso 3.

    Qu aristas son puentes en el grafo mostrado?

    Ejercicios. Determine si los siguientes grafos son eulerianos y/o semieulerianos.

    Grafo 1

    Grafo 2

    Grafo 3

    Grafo 4

    También podría gustarte