Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 293 vistas

    Maco U3 A3 V2 Nofp

    Cargado por

    norberto ferrales
    Sea G=(V,A) una gráfica conexa, sin lazos y no dirigida. Demuestra que el número Cromático de G es 2 si y solo si G es una gráfica bipartita.

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd

    Maco U3 A3 V2 Nofp

    Cargado por

    norberto ferrales
    293 vistas3 páginas
    Sea G=(V,A) una gráfica conexa, sin lazos y no dirigida. Demuestra que el número Cromático de G es 2 si y solo si G es una gráfica bipartita.

    Título original

    MACO_U3_A3_V2_NOFP

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    DOCX, PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Sea G=(V,A) una gráfica conexa, sin lazos y no dirigida. Demuestra que el número Cromático de G es 2 si y solo si G es una gráfica bipartita.

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    293 vistas3 páginas

    Maco U3 A3 V2 Nofp

    Cargado por

    norberto ferrales
    Sea G=(V,A) una gráfica conexa, sin lazos y no dirigida. Demuestra que el número Cromático de G es 2 si y solo si G es una gráfica bipartita.

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    de 3

    División de Ciencias Exactas, Ingeniería y Tecnología

    Licenciatura en Matemáticas

    Asignatura: Análisis Combinatorio.

    Unidad 3. Teoría de Gráficas.

    Actividad 3.

    Planaridad y Coloraciones.

    Grupo: MT-MACO-2002-B1-001

    Alumno: Norberto Ferrales Portillo

    Matrícula: ES1821015206

    Docente: Sergio Cesar Alejandro Gutiérrez Guzmán

    Agosto 2020
    ACTIVIDAD 3. Planaridad y coloraciones.
    Propósito: En esta actividad resolverás ejercicios y problemas sobre planaridad y
    coloraciones.
    1. Sea G=(V,A) una gráfica conexa, sin lazos y no dirigida. Demuestra que
    el número Cromático de G es 2 si y solo si G es una gráfica bipartita.

    Para su demostración usaremos la doble implicación de que x (G)=2 es


    bipartita y viceversa

    Por lo tanto Sea G=(V , A) una gráfica conexa, sin

    lazos y no dirigida siendo x (G)=2 con 2 clases cromáticas y por lo tanto 2


    conjuntos independientes y disjuntos U , V donde:
    U ∪V =G
    U ∩V =∅
    De manera que las aristas sólo pueden conectar vértices de un conjunto con vértices del
    otro por lo que induce a la bipartición de G.

    Por otro lado si G es bipartita obtenemos los conceptos antes descritos donde

    U ∪V =G
    U ∩V =∅
    ∀ v 1 , v 2 ∈ V , ∀ u1 ,u 2 ∈U no existe ninguna ariste e=( u1 , u2 ) ∋e=(v 1 , v 2).

    Por lo que al asignar coloración a los 2 conjuntos disjuntos U , V tendremos una 2-

    coloración para G siendo 2 el menor entero k tal que la gráfica G es k-coloreable.


    Al igual, dado que no existe una arista con dos vértices del mismo conjunto por lo

    que las únicas aristas existente son la que conecta los vértices de U , V siendo 2 el
    menor número para los 2 clases cromáticas existentes.
    Bibliografía
    Gonzalez-Moreno, D. D. (1 de Abril de 2017). Universidad Autónoma Metropolitana de
    Cuajimalpa. Obtenido de
    http://www.cua.uam.mx/pdfs/conoce/libroselec/24Libro_Introduccion_a_la_teoria_d
    e_las_gra.pdf

    Ralph, G. (1962). El Principio de inclusión y exclusión. En G. Ralph, Matemáticas discretas y


    combinatoria (págs. 403-431). México: Prentice Hall.

    Richard Johnsonbaugh. (2005). Matemáticas Discretas. En R. Johnsonbaugh, Matemáticas


    Discretas (pág. 291). México: Pearson Educación.

    También podría gustarte