Boss

Nombre… Mario Victor Garcia Reynoso.

Materia… Matematicas Discretas.

Trabajo…

Teoremas en teoría de grafos…

Maestro… Jesús Ballesteros.

Indice..

Introducción………………………………………..1

Teoremas(1-9)……………………………………..2

Teorema de los cuatro colores………………3

Conclusión……………………………………………4

Bibliografía…………………………………………...5

Introducción….
La teoría de grafos tiene su origen en elproblema de los siete puentes de Königsberg resuelto por Leonhard Euler.
Más tarde, otros problemas influyeron en el desarrollo de la teoría de grafos como el estudio de las redes eléctricas, la enumeración de isómeros de hidrocarburos,...
Hoy en día es rara la disciplina científica o humanística que no utiliza la teoría de grafos. Como ejemplos podemos citar la psicología en dinámica de grupos,la sociología en los sociogramas, la física teórica, que usa los diagramas de Feynmann, donde se representan mediante líneas las partículas elementales, el estudio de flujos en redes en programación lineal e investigación operativa, los cambios de variable en el cálculo diferencial...
Teorema 1 Pruebe que en un grafo la suma de los grados de los vértices es
el doble delnúmero de lados. Es decir, si G = (V , E) es el grafo, entonces

u∈V
gr(u) = 2
|E|

Teorema 2 Si G = (V , E) es un digrafo, entonces

u∈V
gr−(u) =

u∈V
gr+(u) =
|E|

Teorema 3 Pruebe que el número devértices de grado impar es par.

Teorema 4 Si en un grafo G todos los vértices tiene grado mayor a 1, pruebe que existe un ciclo.

Teorema 5 Existe una cadena de u a v si y sólo si existe un camino simple de u a v.

Teorema 6 Si G es conexo y e es un puente de G, pruebe que G
− e tiene dos componentes conexas.Teorema 7 Suponga que G se puede recorrer y que γ es un recorrido total que no empieza ni termina en el vértice u. Pruebe que el grado de u es par.
Un grafo (multigrafo) es euleriano si existe un recorrido total cerrado.

Teorema 8 Un grafo finito conexo es euleriano si y sólo si cada vértice tiene grado par.
Pruebe que cualquiergrafo conexo finito con dos vértices de grado impar tiene un recorrido total.

Teorema 9 (Euler) Si G es un grafo planar conexo, entonces cualquier representación planar de G tiene r = e − v + 2 regiones donde e es el número de lados y v el número de vértices.Teorema de los cuatro colores: Cuatro colores son siempre suficientes para colorear el un mapa.

El mapa siguiente muestra que tres colores no bastan: Si se empieza por el país central a y se esfuerza uno en utilizar el menor número de colores, entonces en la corona alrededor de a alternan dos colores. Llegando al país h se tiene que introducir un cuarto color. Lomismo sucede en i si se emplea el mismo método.

La forma precisa de cada país no importa; lo único relevante es saber cual país toca cual otro.

Estos datos están incluidos en el grafo donde los vértices son los países y las aristas conectan los que justamente son adyacentes. Entonces la cuestión equivale a atribuir a cada vértice un color distinto del de sus vecinos.

Hemos visto que trescolores no son suficientes, y demostrar que con cinco siempre se llega, es bastante fácil. Pero el teorema de los cuatro colores no es nada obvio. prueba de ello es que se ha tenido que emplear los ordenadores para acabar la demostración (se ha hecho un programa que permitió verificar una multitud de casos, lo que ahorró muchísimo tiempo a los matemáticos). Fue la primera vez que la comunidad...