Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 97 vistas

    Numero Cromatico

    Cargado por

    LionKing093
    Este documento presenta información sobre la coloración de grafos, incluyendo definiciones de términos como adyacencia, incidencia y ponderación. Explica que la coloración de grafos asigna colores a los vértices, aristas o regiones de un grafo de tal manera que elementos adyacentes tengan colores diferentes. También describe propiedades del número cromático, como que para un grafo completo se necesitan tantos colores como vértices tiene el grafo.

    Copyright:

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

    Numero Cromatico

    Cargado por

    LionKing093
    97 vistas6 páginas
    Este documento presenta información sobre la coloración de grafos, incluyendo definiciones de términos como adyacencia, incidencia y ponderación. Explica que la coloración de grafos asigna colores a los vértices, aristas o regiones de un grafo de tal manera que elementos adyacentes tengan colores diferentes. También describe propiedades del número cromático, como que para un grafo completo se necesitan tantos colores como vértices tiene el grafo.

    Descripción original:

    Numero cromatico, coloracion de vertices aristas, Coloracion de Regiones.

    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?

    Este documento presenta información sobre la coloración de grafos, incluyendo definiciones de términos como adyacencia, incidencia y ponderación. Explica que la coloración de grafos asigna colores a los vértices, aristas o regiones de un grafo de tal manera que elementos adyacentes tengan colores diferentes. También describe propiedades del número cromático, como que para un grafo completo se necesitan tantos colores como vértices tiene el grafo.

    Copyright:

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

    Numero Cromatico

    Cargado por

    LionKing093
    Este documento presenta información sobre la coloración de grafos, incluyendo definiciones de términos como adyacencia, incidencia y ponderación. Explica que la coloración de grafos asigna colores a los vértices, aristas o regiones de un grafo de tal manera que elementos adyacentes tengan colores diferentes. También describe propiedades del número cromático, como que para un grafo completo se necesitan tantos colores como vértices tiene el grafo.

    Copyright:

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

    Repblica Bolivariana de Venezuela

    Ministerio Del Poder Popular Para La Defensa


    Universidad Nacional Experimental Politcnica De La
    Fuerza Armada Nacional
    UNEFA, Ncleo Vargas
    V Semestre, Ingeniera De Sistemas.

    NUMERO
    CROMATICO

    Integrante:
    Kleiber

    Catia la mar, 25 de octubre del 2017


    Propiedades

    Adyacencia:

    Dos aristas son adyacentes si tienen un vrtice en comn, y dos vrtices son
    adyacentes si una arista los une.

    Incidencia:

    Una arista es incidente a un vrtice si sta lo une a otro.

    Ponderacin:

    Corresponde a una funcin que a cada arista le asocia un valor (costo, peso,
    longitud, etc.), para aumentar la expresividad del modelo. Esto se usa mucho para
    problemas de optimizacin, como el del vendedor viajero o del camino ms corto.

    Etiquetado: distincin que se hace a los vrtices y/o aristas mediante una marca
    que los hace unvocamente distinguibles del resto.
    Numero cromtico

    Una coloracin que usa a lo ms k colores se llama k-coloracin (propia). El


    menor nmero de colores necesarios para colorear un grafo G se llama nmero
    cromtico y se denota como (G). Un grafo que puede ser asignada una k-
    coloracin (propia) es k-coloreable y es k-cromtico si su nmero cromtico es
    exactamente k. Un subconjunto de vrtices asignados con el mismo color se llama
    una clase de color. Cada clase forma un conjunto independiente. Esto es, una k-
    coloracin es lo mismo que una particin del conjunto de vrtices en k conjuntos
    independientes, y los trminos k-partito y k-coloreable tienen el mismo significado.
    Coloracin de grafos aristas, vrtices y regiones

    Una coloracin de vrtices para el grafo de Petersen utilizando tres colores,


    el nmero mnimo posible.

    En Teora de grafos, la coloracin de grafos es un caso especial de


    etiquetado de grafos; es una asignacin de etiquetas llamadas colores a elementos
    del grafo. De manera simple, una coloracin de los vrtices de un grafo tal que
    ningn vrtice adyacente comparta el mismo color es llamado vrtice coloracin.
    Similarmente, una arista coloracin asigna colores a cada arista tal que aristas
    adyacentes no compartan el mismo color, y una coloracin de caras de un grafo
    plano a la asignacin de un color a cada cara o regin tal que caras que compartan
    una frontera comn tengan colores diferentes. El vrtice coloracin es el punto de
    inicio de la coloracin, y los otros problemas de coloreo pueden ser transformados
    a una versin con vrtices. Por ejemplo, una arista coloracin de un grafo es
    justamente una vrtice coloracin del grafo lnea respectivo, y una coloracin de
    caras de un grafo plano es una vrtice coloracin del grafo dual.

    La convencin de usar colores se origina de la coloracin de pases de un


    mapa, donde cada cara es literalmente coloreada. Esto fue generalizado a la
    coloracin de caras de grafos inmersos en el plano. En representaciones
    matemticas y computacionales se utilizan tpicamente enteros no negativos como
    colores. En general se puede usar un conjunto finito como conjunto de colores. La
    naturaleza del problema de coloracin depende del nmero de colores pero no
    sobre cuales son.
    Propiedades de la coloracin del grafo:

    Entre las propiedades del nmero cromtico, se pueden mencionar las


    siguientes:

    Para un grafo completo , . Esto se puede ver intuitivamente,


    ya que un grafo completo tiene todos sus nodos conectados entre s, es

    decir,

    Por lo tanto, como un coloreo vlido obliga a que dos nodos adyacentes
    tengan colores distintos, se necesitan n colores distintos para formar un coloreo

    vlido de G, y este es el menor nmero posible. Luego,

    Si G es un ciclo de longitud par, entonces

    Si G es un ciclo de longitud impar, entonces

    Para todo grafo G, , donde corresponde al valor de la


    cliqu de mayor orden de un grafo.

    Para todo grafo G, ,

    donde es el mximo entre los grados de todos los nodos (es decir, el
    grado mximo).

    También podría gustarte