Algunos Ejercicios de Grafos

Ejercicio Nro 01

  void PresentarGrafo(tgrafo g)

{

   tnodo n;

   tarco a;

   n=PrimerNodo(g);

   while (n!=Nulo) {

      a=PrimerArco(n,g);

      while (a!=Nulo) {

         printf(\"%s -> %s \",a->origen->etiq,a->destino->etiq);

         printf(\" (%f)\\n\",a->valor);

         a=SiguienteArco(n,a,g);

      }

      n=SiguienteNodo(n,g);

   }

}

Ejercicio Nro 02

void InsertarNodo(tetq dato, tgrafo g)

{

   tnodo aux,p;

   aux = (tnodo)malloc(sizeof(struct nodo));

   if (aux == NULL)

      error(\"Error Memoria Insuficiente.\");

   else {

      p=g;

      while(p->sig != NULL)

         p = p->sig;

      aux->etiq = (char *)malloc(sizeof (char)*TE);"+

      if (aux->etiq == NULL)

         error(\"Error Memoria Insuficiente.\");

      aux->nodo = p->nodo+1;

      strcpy(aux->etiq,dato);+

      aux->ady = NULL;

      aux->inc = NULL;

      aux->sig = NULL;

      p->sig = aux;

      g->nodo++;

   }

Ejercicio Nro 03

tgrafo DesconectarNodo(tnodo a_eliminar,tgeafo g)

{

   tgrafo g_nd;

   tnodo n;

   tnodo org;dst;

   tnodo o,d;

   tarco a;

   g_nd = Crear();

   for (n=PrimerNodo(g); n!=NULL; n=SiguienteNodo(n,g))

                  InsertarNodo(Etiqueta(n,g),g_nd);

   for (n=PrimerNodo(g); n!=NULL; n=SiguienteNodo(n,g))

                 for (a=PrimerArco(n,g); a!=NULL; a=SiguienteArco(n,a,g)) {

                               org = NodoOrigen(a,g);

                               dst = NodoDestino(a,g);

        if ((org!=a_eliminar) && dst!=a_eliminar)) {

                   o = LocalizaLabel(Label(org,g), g_nd);

                                  d = LocalizaLabel(Label(dst,g), g_nd);

                                  InsertarArco(o,d,g_nd);                          

        }

     }

                 return g_nd;

}

Teorema de los Cuatro Colores

Otro problema famoso relativo a los grafos: ¿Cuántos colores son necesarios para dibujar un mapa político, con la condición obvia que dos países adyacentes no puedan tener el mismo color? Se supone que los países son de un solo pedazo, y que el mundo es esférico o plano. En un mundo en forma de toroide; el teorema siguiente no es válido:

Cuatro colores son siempre suficientes para colorear 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. Lo mismo sucede en i si se emplea el mismo método.

La forma precisa de cada país no importa; lo único relevante es saber qué país toca a qué 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 tres colores 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 han tenido que emplear 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 matemática aceptó una demostración asistida por ordenador, lo que ha creado una fuerte polémica dentro de la comunidad matemática, llegando en algunos casos a plantearse la cuestión de que esta demostración y su aceptación es uno de los momentos que han generado una de las más terribles crisis en el mundo matemático.

Caracterización de Grafos

Grafos simples

Un grafo es simple si sólo 1 arista QUE une dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos.

Un grafo que no es simple se denomina Multigráfica o Gráfo múltiple.

Grafos conexos

Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b.

Un grafo es doblemente conexo si cada par de vértices está conectado por al menos dos caminos disjuntos; es decir, es conexo y no existe un vértice tal que al sacarlo el grafo resultante sea disconexo.

Es posible determinar si un grafo es conexo usando un algoritmo Búsqueda en anchura (BFS) o Búsqueda en profundidad (DFS).

En términos matemáticos la propiedad de un grafo de ser (fuertemente) conexo permite establecer con base en él una relación de equivalencia para sus vértices, la cual lleva a una partición de éstos en "componentes (fuertemente) conexas", es decir, porciones del grafo, que son (fuertemente) conexas cuando se consideran como grafos aislados. Esta propiedad es importante para muchas demostraciones en teoría de grafos.

Grafos completos

Un grafo es completo si existen aristas uniendo todos los pares posibles de vértices. Es decir, todo par de vértices (a, b) debe tener una arista e que los une.

El conjunto de los grafos completos es denominado usualmente , siendo el grafo completo de n vértices.

Un , es decir, grafo completo de n vértices tiene exactamente aristas.

La representación gráfica de los como los vértices de un polígono regular da cuenta de su peculiar estructura.

Grafos bipartitos

Un grafo G es bipartito si puede expresarse como (es decir, sus vértices son la unión de dos grupos de vértices), bajo las siguientes condiciones:

• V₁ y V₂ son disjuntos y no vacíos.
• Cada arista de A une un vértice de V₁ con uno de V₂.
• No existen aristas uniendo dos elementos de V₁; análogamente para V₂.

Bajo estas condiciones, el grafo se considera bipartito, y puede describirse informalmente como el grafo que une o relaciona dos conjuntos de elementos diferentes, como aquellos resultantes de los ejercicios y puzzles en los que debe unirse un elemento de la columna A con un elemento de la columna B.

Teoría de los Grafos

             En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas). Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas (edges en inglés) que pueden ser orientados o no. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).

Variantes de definiciones de grafos y propiedades

 Variantes sobre las definiciones principales

Algunas aplicaciones requieren extensiones más generales a las dos propuestas clásicas de grafos. Aunque la definición original los permite, según la aplicación concreta pueden ser válidos o no. A veces V o E pueden ser un multiconjunto, pudiendo haber más de una arista entre cada par de vértices. La palabra grafo (a secas) puede permitir o no múltiples aristas entre cada par de vértices, dependiendo del autor de la referencia consultada. Si se quiere remarcar la inexistencia de múltiples aristas entre cada par de vértices (y en el caso no dirigido, excluir bucles) el grafo puede llamarse simple. Por otra parte, si se quiere asegurar la posibilidad de permitir múltiples aristas, el grafo puede llamarse multigrafo (a veces se utiliza el término pseudografo para indicar que se permiten tanto bucles como múltiples aristas entre cada par de vértices).

 Propiedades

• Adyacencia: dos aristas son adyacentes si tienen un vértice en común, y dos vértices son adyacentes si una arista los une.
• Incidencia: una arista es incidente a un vértice si ésta lo une a otro.
• Ponderación: corresponde a una función 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 optimización, como el del vendedor viajero o del camino más corto.
• Etiquetado: distinción que se hace a los vértices y/o aristas mediante una marca que los hace unívocamente distinguibles del resto.

Origen y definición de Grafo

El origen de la palabra grafo es griego y su significado etimológico es "trazar". Aparece con gran frecuencia como respuesta a problemas de la vida cotidiana, algunos ejemplos podrían ser los siguientes: un gráfico de una serie de tareas a realizar indicando su secuenciación (un organigrama), grafos matemáticos que representan las relaciones binarias, una red de carreteras, la red de enlaces ferroviarios o aéreos o la red eléctrica de una ciudad. En cada caso, es conveniente representar gráficamente el problema dibujando un grafo como un conjunto de puntos (vértices) con líneas conectándolos (arcos). 

Ahora bien, un grafo G es un par ordenado G = (V,E), donde:

• V es un conjunto de vértices o nodos, y
• E es un conjunto de arcos o aristas, que relacionan estos nodos.

Normalmente V suele ser finito. Muchos resultados importantes sobre grafos no son aplicables para grafos infinitos. Se llama orden de G a su número de vértices, | V | .