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
    Está en la página 1de 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

    • Maco U2 A2 V1 Jome
      Documento4 páginas
      Maco U2 A2 V1 Jome
      juan meza
      Aún no hay calificaciones
    • EA - AnaÌlisis y Prediccion
      Documento3 páginas
      EA - AnaÌlisis y Prediccion
      Monserratt Téllez
      100% (1)
    • Retos matemáticos con soluciones
      De Everand
      Retos matemáticos con soluciones
      Juan Flaquer
      3.5/5 (8)
    • Mcom2 U1 A2 Jeru
      Documento5 páginas
      Mcom2 U1 A2 Jeru
      Jesús Úrzulo
      Aún no hay calificaciones
    • Mcom2 U1 A3 Jeru
      Documento18 páginas
      Mcom2 U1 A3 Jeru
      Jesús Úrzulo
      Aún no hay calificaciones
    • Mcom2 U2 A2 Elvc
      Documento4 páginas
      Mcom2 U2 A2 Elvc
      jose calderon
      Aún no hay calificaciones
    • Mamt2 U3 A2 Lapb
      Documento9 páginas
      Mamt2 U3 A2 Lapb
      Laura Pontón Becerril
      Aún no hay calificaciones
    • Maco U2 A3 V1 Jome
      Documento4 páginas
      Maco U2 A3 V1 Jome
      juan meza
      Aún no hay calificaciones
    • Mamt1 U1 A2
      Documento3 páginas
      Mamt1 U1 A2
      Fer Màrquez
      Aún no hay calificaciones
    • Mpro3 U2 A2 Raic PDF
      Documento2 páginas
      Mpro3 U2 A2 Raic PDF
      Raúl Sánchez
      Aún no hay calificaciones
    • Mcom2 U2 A2 Jeru
      Documento6 páginas
      Mcom2 U2 A2 Jeru
      Jesús Úrzulo
      Aún no hay calificaciones
    • MACO - U3 - A2 - AUPC. Árboles
      Documento6 páginas
      MACO - U3 - A2 - AUPC. Árboles
      Zankass P. Coria
      Aún no hay calificaciones
    • Mcom2 U1 Ea Jeru
      Documento18 páginas
      Mcom2 U1 Ea Jeru
      Jesús Úrzulo
      Aún no hay calificaciones
    • Maco U2 Ea
      Documento5 páginas
      Maco U2 Ea
      Fer Màrquez
      100% (1)
    • Maco U3 A2 Lapb
      Documento4 páginas
      Maco U3 A2 Lapb
      Laura Pontón Becerril
      Aún no hay calificaciones
    • Manu2 U1 Ea
      Documento9 páginas
      Manu2 U1 Ea
      Aisha Gutierrez Lugo
      Aún no hay calificaciones
    • Mpes U2 Ea Davc
      Documento7 páginas
      Mpes U2 Ea Davc
      Daniel Villalobos
      Aún no hay calificaciones
    • Maco U2 A2 Lapb
      Documento16 páginas
      Maco U2 A2 Lapb
      Laura Pontón Becerril
      100% (1)
    • Mmes U1 Ea Lapb 2
      Documento34 páginas
      Mmes U1 Ea Lapb 2
      Laura Pontón Becerril
      Aún no hay calificaciones
    • Mest3 U1 A2 Raic
      Documento4 páginas
      Mest3 U1 A2 Raic
      Raúl Sánchez
      Aún no hay calificaciones
    • Mcom2 U3 A1 Jeru
      Documento3 páginas
      Mcom2 U3 A1 Jeru
      Jesús Úrzulo
      Aún no hay calificaciones
    • Mcom2 U3 A3 Malr
      Documento3 páginas
      Mcom2 U3 A3 Malr
      Peque Fresita Lopez
      Aún no hay calificaciones
    • Mamt2 U1 A2 Raic
      Documento4 páginas
      Mamt2 U1 A2 Raic
      Raúl Sánchez
      Aún no hay calificaciones
    • Mest3 U3 A1 FRCR
      Documento9 páginas
      Mest3 U3 A1 FRCR
      soundwave72
      Aún no hay calificaciones
    • Maco U1 A1 Lapb
      Documento20 páginas
      Maco U1 A1 Lapb
      Laura Pontón Becerril
      Aún no hay calificaciones
    • Maco U3 Ea Unadm
      Documento5 páginas
      Maco U3 Ea Unadm
      sergio651212
      Aún no hay calificaciones
    • Mvco1 U4 A2 CLRM
      Documento18 páginas
      Mvco1 U4 A2 CLRM
      Claudio Ramón Rodriguez Mondragón
      Aún no hay calificaciones
    • Mest3 U1 Ea Anom
      Documento4 páginas
      Mest3 U1 Ea Anom
      Ana Yansy Olarte Mendoza
      Aún no hay calificaciones
    • Medp U3 A3 Jomh
      Documento6 páginas
      Medp U3 A3 Jomh
      JOEL ALBERTO MONTALVO HERNANDEZ
      Aún no hay calificaciones
    • Mest3 U2 A2 Mamc
      Documento8 páginas
      Mest3 U2 A2 Mamc
      Isabel Muñoz
      100% (1)
    • Maco U2 Ea Lapb
      Documento10 páginas
      Maco U2 Ea Lapb
      Laura Pontón Becerril
      Aún no hay calificaciones
    • Mamt2 U4 Ac Jeru
      Documento3 páginas
      Mamt2 U4 Ac Jeru
      Jesús Úrzulo
      Aún no hay calificaciones
    • Mpes U3 Ea Elvc
      Documento5 páginas
      Mpes U3 Ea Elvc
      jose calderon
      Aún no hay calificaciones
    • Mest3 U3 Ea FRCR
      Documento4 páginas
      Mest3 U3 Ea FRCR
      soundwave72
      Aún no hay calificaciones
    • Maco U3 Ac Elvc
      Documento3 páginas
      Maco U3 Ac Elvc
      jose calderon
      Aún no hay calificaciones
    • Mamt2 U4 Ea Lapb
      Documento11 páginas
      Mamt2 U4 Ea Lapb
      Laura Pontón Becerril
      100% (1)
    • Manu2 U1 A1 Jomh
      Documento5 páginas
      Manu2 U1 A1 Jomh
      JoelAlbertoMontalvoHernandez
      Aún no hay calificaciones
    • Mamd1 U1 A2 Luac
      Documento5 páginas
      Mamd1 U1 A2 Luac
      Luis Gerardo Aguilar
      Aún no hay calificaciones
    • Mamt1 U1 A2 Raga
      Documento3 páginas
      Mamt1 U1 A2 Raga
      Rafael Guillermo G. Acuña
      Aún no hay calificaciones
    • Mamd1 U2 A3 V1 Poar PDF
      Documento2 páginas
      Mamd1 U2 A3 V1 Poar PDF
      Alejandro
      100% (1)
    • Mamt2 U3 A1 Jeru
      Documento4 páginas
      Mamt2 U3 A1 Jeru
      Jesús Úrzulo
      Aún no hay calificaciones
    • Mpes U3 A4 Jome
      Documento7 páginas
      Mpes U3 A4 Jome
      juan meza
      Aún no hay calificaciones
    • U3. Independencia Del Postulado de Las Paralelas PDF
      Documento50 páginas
      U3. Independencia Del Postulado de Las Paralelas PDF
      Tareas Matematicas
      Aún no hay calificaciones
    • Maco U1 A2 Calv
      Documento5 páginas
      Maco U1 A2 Calv
      charlyshaka
      Aún no hay calificaciones
    • Manu1 U2 A2 Doys
      Documento5 páginas
      Manu1 U2 A2 Doys
      Isabel Muñoz
      Aún no hay calificaciones
    • Mamd1 U1 A2 Alrq
      Documento5 páginas
      Mamd1 U1 A2 Alrq
      Watermelon Ruan
      Aún no hay calificaciones
    • Mamt2 U4 A2 Raic
      Documento4 páginas
      Mamt2 U4 A2 Raic
      Raúl Sánchez
      Aún no hay calificaciones
    • Mcom2 U2 A1 Jeru
      Documento5 páginas
      Mcom2 U2 A1 Jeru
      Jesús Úrzulo
      Aún no hay calificaciones
    • Mvco2 U1 A2 Jops
      Documento2 páginas
      Mvco2 U1 A2 Jops
      Josuè Priego Sanabria
      Aún no hay calificaciones
    • Mamd1 U2 A2 Luac
      Documento4 páginas
      Mamd1 U2 A2 Luac
      Luis Gerardo Aguilar Cruz
      Aún no hay calificaciones
    • Mamt2 U1 A1
      Documento33 páginas
      Mamt2 U1 A1
      Claudio Ramón Rodriguez Mondragón
      Aún no hay calificaciones
    • Mvaco2 U2 Ea Jomh
      Documento7 páginas
      Mvaco2 U2 Ea Jomh
      JoelAlbertoMontalvoHernandez
      Aún no hay calificaciones
    • Mcom2 U3 A2 Malr
      Documento3 páginas
      Mcom2 U3 A2 Malr
      Peque Fresita Lopez
      Aún no hay calificaciones
    • Mpes U2 A1 Jeru
      Documento4 páginas
      Mpes U2 A1 Jeru
      Jesús Úrzulo
      Aún no hay calificaciones
    • Mpes U2 A4 Davc
      Documento5 páginas
      Mpes U2 A4 Davc
      Daniel Villalobos
      Aún no hay calificaciones
    • Mvco2 U3 A2 V2 Raic
      Documento6 páginas
      Mvco2 U3 A2 V2 Raic
      Raúl Sánchez
      Aún no hay calificaciones
    • Manu2 U3 A1 Arna
      Documento11 páginas
      Manu2 U3 A1 Arna
      Arturo Nava
      Aún no hay calificaciones
    • Aplicaciones Grafos
      Documento4 páginas
      Aplicaciones Grafos
      Pascual Onofre
      Aún no hay calificaciones
    • Practica de Matematica Discreta
      Documento8 páginas
      Practica de Matematica Discreta
      Alex Navez Mariños
      Aún no hay calificaciones
    • Introducción a las ecuaciones y las inecuaciones
      De Everand
      Introducción a las ecuaciones y las inecuaciones
      Simone Malacrida
      Aún no hay calificaciones