Hoja 1
Capítulo 7: Grafos
  Introducción
    -Son representaciones de las redes, y por medio de ellos se puede expresar en forma visual y sencilla la relación entre elementos de distinto tipo
-Uno de los primeros resultados de la teoría de grafos fue el que obtuvo Leonhard Euler en el siglo XVIII al resolver el problema de los puentes de Königsberg
-Este problema consiste en recorrer 7 puentes que conectan 4 porciones de tierra, con la condición de pasar por cada puente una sola vez
  Partes de un grafo
    -Es un diagrama que consta de un conjunto de vértices y un conjunto de datos
-los elementos de un grafo constan de vértices, lados, lados paralelos, lazo y valencia de un vértice
  Tipos de grafo
    -Grafo simple: Son aquellos grafos que no tienen lazos ni lados paralelos
-Grafo completo de n vértices (K,,): Es el grafo en donde cada vértice está relacionado con todos los demás, sin lazos ni lados paralelos
-Complemento de un grafo: Es el grafo que le falta al grafo G, de forma que entre ambos forman un grafo completo de n vértices.
-Grafo bipartido: Es el grafo que está compuesto por dos conjuntos de vértices, en donde los elementos del conjunto A se relacionan con los del conjunto B, pero entre los vértices de un mismo conjunto no existe arista que los una
-Grafo bipartido completo (Kn,m): Es el grafo que está compuesto por dos conjuntos de vértices, y en el que cada vértice de A está unido con todos los vértices de B, pero entre los vértices de uno mismo no existe arista que los una
  Representación matricial
    -Permite una rápida y clara manipulación de la información, así como el determinar algunas propiedades de los grafos que de otra manera serían más difíciles de obtener
-Matriz de adyacencia: Es una matriz cuadrada en la cual los vértices del grafo se indican como filas y como columnas
-Matriz de incidencia: En esta matriz se colocan los vértices del grafo como filas y las aristas como columnas
  Caminos y circuitos
    -Se puede recorrer la información de diferente manera, lo cual implica seguir distintas rutas para llegar de un modo del grafo a otro
-Camino: Es una sucesión de lados que van de un vértice x a un vértice w
-Circuito: Es un camino del vértice w al vértice w; esto es, un camino que regresa al mismo vértice de donde salió
-Circuito simple de longitud: Es aquel camino del vértice w al vértice w que solamente tiene un ciclo en la ruta que sigue
-Camino simple de longitud: Es una sucesión de lados que van de un vértice x a un vértice w, en donde los lados que componen dicho camino son distintos e iguales a n
  Isomorfismo
    -Se dice que dos grafos 𝐺_1 y 𝐺_2 son isomorfos cundo teniendo apariencia diferente realmente son iguales porque coinciden en el número de lados, número de vértices, conjunto de valencias, ser o no conexos, número de circuitos de longitud n y tener o no un circuito de Euler
  Grafos planos
    -Un grafo plano es aquel que se puede dibujar en un solo plano y cuyas aristas no se cruzan entre sí
  Coloración de datos
    -La coloración de los vértices V del grafo usando un color del conjunto C se encuentra dada por la función
-Esto implica que cuando se lleva a cabo la coloración en vértices de un grafo, cada par de vértices adyacentes 𝑣_1 y 𝑣_2 del grafo deberán estar iluminados con un color diferente
  Número cromático
    -Se llama número cromático del grafo G al número mínimo de colores con que se puede colorear un grafo cuidando que los vértices adyacentes no tengan el mismo color
  Coloración de grafos planos
    -Todo mapa puede ser representado por un grafo plano, en donde cada parte del mapa representa un vértice
-En el grafo también se debe incluir la parte que rodea el mapa como un vértice adicional, ya que es adyacente a varias partes del mapa
  Polinomio cromático
    -Al número de formas en que se puede colorear el grafo G usando para ello w colores se llama polinomio cromático de G
  Aplicación de los grafos
    -Existe una relación entre los distintos elementos que integran un sistema, trabajo o equipo
-permiten modelar todo aquello que está relacionado, es evidente que su aplicación es muy amplia y variada
  Reconocimiento de patrones mediante grafos de similaridad
    -Los grafos de similaridad permiten agrupar información con características semejantes
-implica formar subgrafos en donde los vértices de un subgrafo están relacionados entre sí, pero no tienen relación con los vértices del otro subgrafo, ya que no son similares
  Determinación de la ruta más corta mediante grafos ponderados
    -En un grafo ponderado a las aristas se les asigna un valor al que se le llama ponderación y que podría representar la distancia que hay de un nodo a otro, o bien el costo de transportarse de una ciudad a otra
-consiste en encontrar el camino más corto para ir de una ciudad origen w a una ciudad destino x