Matematicas Discretas

Matematicas Discretas

UNIDAD V. TEORÍA DE GRAFOS

Competencias genéricas

• Capacidad de aplicar los conocimientos en la práctica.
• Habilidades para buscar, procesar, abstraer, analizar y sintetizar información procedente de fuentes diversas.
• Capacidad de trabajo en equipo y de investigación.

Competencia específica Aplica los conceptos básicos de grafos para resolver problemas afines al área computacional, relacionados con el recorrido, búsqueda y ordenamiento en grafos.

Pares Ordenados

Un par ordenado consta de dos elementos (x, y), donde:

Conjunto Producto

5.1 ELEMENTOS, CARACTERÍSTICAS Y COMPONENTES

Grafos

EJEMPLOS DE Grafos

5.2 REPRESENTACIÓN DE LOS GRAFOS

Problema de los puentes de Königsberg

Grafos Conexos

Caminos de Euler

Grafos

Valencia de nodos

Representación Matricial de Grafos

5.2 REPRESENTACIÓN DE LOS GRAFOS

Teorema de Euler y Kuratwski

Grafos Isomorfos

Grafo Plano

Grafo Homeomorfo

FIN

Longitud de un camino

Referencias

5.Lorem ipsum dolor sit

2.Lorem ipsum dolor sit

3.Lorem ipsum dolor sit

4.Lorem ipsum dolor sit

6.Lorem ipsum dolor sit

1.Lorem ipsum dolor sit

INTEGRANDES DEL EQUIPO

MEDINA VAZQUEZ JADE ALEXANDRAOSORIO GONZALEZ LIUDMILE MARLENE TORRES TUZ ALAN WILLEBALDOZANCHEZ ZAVALA MARIA ALEXANDRA

¿Qué es?

En teoría de grafos, la longitud de un camino es el número de aristas que se recorren entre un vértice inicial y uno final. En grafos ponderados, se obtiene sumando el peso de cada arista recorrida.

Tipos de conteo según el grafoGrafos no ponderados:

• Grafos no ponderados: cada arista vale 1 unidad.
• Grafos ponderados: cada arista tiene un peso o valor.
• Ciclos: el camino inicia y termina en el mismo vértice.

¿Tienes una idea?

Usa este espacio para añadir una interactividad genial. Incluye texto, imágenes, vídeos, tablas, PDFs… ¡incluso preguntas interactivas! Tip premium: Obten información de cómo interacciona tu audiencia:

• Visita las preferencias de Analytics;
• Activa el seguimiento de usuarios;
• ¡Que fluya la comunicación!

¿Tienes una idea?

Usa este espacio para añadir una interactividad genial. Incluye texto, imágenes, vídeos, tablas, PDFs… ¡incluso preguntas interactivas! Tip premium: Obten información de cómo interacciona tu audiencia:

• Visita las preferencias de Analytics;
• Activa el seguimiento de usuarios;
• ¡Que fluya la comunicación!

Caminos de Euler

Los caminos de Euler son recorridos en un gráfico donde cada borde se recorre exactamente una vez. Un circuito de Euler es un camino de Euler que comienza y termina en el mismo vértice. La teoría de los caminos de Euler fue desarrollada por Leonhard Euler y se relaciona con el famoso problema de los Siete Puentes de Königsberg. Para que un gráfico tenga caminos de Euler, todos los vértices deben tener un grado par. Si hay vértices de grado impar, el gráfico puede ser semi-euleriano, con un camino de Euler que comienza en un vértice de grado impar y termina en otro.

¿Tienes una idea?

Usa este espacio para añadir una interactividad genial. Incluye texto, imágenes, vídeos, tablas, PDFs… ¡incluso preguntas interactivas! Tip premium: Obten información de cómo interacciona tu audiencia:

• Visita las preferencias de Analytics;
• Activa el seguimiento de usuarios;
• ¡Que fluya la comunicación!

¿Tienes una idea?

Usa este espacio para añadir una interactividad genial. Incluye texto, imágenes, vídeos, tablas, PDFs… ¡incluso preguntas interactivas! Tip premium: Obten información de cómo interacciona tu audiencia:

• Visita las preferencias de Analytics;
• Activa el seguimiento de usuarios;
• ¡Que fluya la comunicación!

¿Tienes una idea?

Usa este espacio para añadir una interactividad genial. Incluye texto, imágenes, vídeos, tablas, PDFs… ¡incluso preguntas interactivas! Tip premium: Obten información de cómo interacciona tu audiencia:

• Visita las preferencias de Analytics;
• Activa el seguimiento de usuarios;
• ¡Que fluya la comunicación!

¿Tienes una idea?

Usa este espacio para añadir una interactividad genial. Incluye texto, imágenes, vídeos, tablas, PDFs… ¡incluso preguntas interactivas! Tip premium: Obten información de cómo interacciona tu audiencia:

• Visita las preferencias de Analytics;
• Activa el seguimiento de usuarios;
• ¡Que fluya la comunicación!

¿Tienes una idea?

Usa este espacio para añadir una interactividad genial. Incluye texto, imágenes, vídeos, tablas, PDFs… ¡incluso preguntas interactivas! Tip premium: Obten información de cómo interacciona tu audiencia:

• Visita las preferencias de Analytics;
• Activa el seguimiento de usuarios;
• ¡Que fluya la comunicación!

¿Tienes una idea?

Usa este espacio para añadir una interactividad genial. Incluye texto, imágenes, vídeos, tablas, PDFs… ¡incluso preguntas interactivas! Tip premium: Obten información de cómo interacciona tu audiencia:

• Visita las preferencias de Analytics;
• Activa el seguimiento de usuarios;
• ¡Que fluya la comunicación!

¿Tienes una idea?

Usa este espacio para añadir una interactividad genial. Incluye texto, imágenes, vídeos, tablas, PDFs… ¡incluso preguntas interactivas! Tip premium: Obten información de cómo interacciona tu audiencia:

• Visita las preferencias de Analytics;
• Activa el seguimiento de usuarios;
• ¡Que fluya la comunicación!

¿Tienes una idea?

Usa este espacio para añadir una interactividad genial. Incluye texto, imágenes, vídeos, tablas, PDFs… ¡incluso preguntas interactivas! Tip premium: Obten información de cómo interacciona tu audiencia:

• Visita las preferencias de Analytics;
• Activa el seguimiento de usuarios;
• ¡Que fluya la comunicación!

GRAFO BIPARTIDO

Grafo Original

Un grafo es bipartido cuando se puede particionar formando dos subconjuntos y se pueden unir formando el grafo original :

Un grafo bipartito es un grafo cuyos vértices se pueden dividir en dos conjuntos disjuntos, de manera que cada arista conecta un vértice de un conjunto con un vértice del otro. Formalmente, para toda arista (u,v) en el grafo, si u pertenece al primer conjunto (V1), entonces v pertenece al segundo conjunto (V2). Los grafos bipartitos son bicoloreables y no contienen ciclos de longitud impar. Se representan comúnmente gráficamente con dos columnas de vértices, donde las aristas conectan vértices de columnas diferentes. Un ejemplo de grafo bipartito es el grafo bipartido completo, donde todos los vértices de uno de los subconjuntos están relacionados con los del otro subconjunto.

¿Tienes una idea?

Usa este espacio para añadir una interactividad genial. Incluye texto, imágenes, vídeos, tablas, PDFs… ¡incluso preguntas interactivas! Tip premium: Obten información de cómo interacciona tu audiencia:

• Visita las preferencias de Analytics;
• Activa el seguimiento de usuarios;
• ¡Que fluya la comunicación!

¿Tienes una idea?

Usa este espacio para añadir una interactividad genial. Incluye texto, imágenes, vídeos, tablas, PDFs… ¡incluso preguntas interactivas! Tip premium: Obten información de cómo interacciona tu audiencia:

• Visita las preferencias de Analytics;
• Activa el seguimiento de usuarios;
• ¡Que fluya la comunicación!

¿Tienes una idea?

Usa este espacio para añadir una interactividad genial. Incluye texto, imágenes, vídeos, tablas, PDFs… ¡incluso preguntas interactivas! Tip premium: Obten información de cómo interacciona tu audiencia:

• Visita las preferencias de Analytics;
• Activa el seguimiento de usuarios;
• ¡Que fluya la comunicación!

¿Tienes una idea?

Usa este espacio para añadir una interactividad genial. Incluye texto, imágenes, vídeos, tablas, PDFs… ¡incluso preguntas interactivas! Tip premium: Obten información de cómo interacciona tu audiencia:

• Visita las preferencias de Analytics;
• Activa el seguimiento de usuarios;
• ¡Que fluya la comunicación!

¿Tienes una idea?

Usa este espacio para añadir una interactividad genial. Incluye texto, imágenes, vídeos, tablas, PDFs… ¡incluso preguntas interactivas! Tip premium: Obten información de cómo interacciona tu audiencia:

• Visita las preferencias de Analytics;
• Activa el seguimiento de usuarios;
• ¡Que fluya la comunicación!

¿Tienes una idea?

Un grafo es conexo o conectado si siempre existe una trayectoria entre cualquier par de nodos.

Un grafo conexo es un grafo en el que todos los vértices están conectados por un camino (en el caso de grafos no dirigidos) o por un semicamino (en el caso de grafos dirigidos). Un grafo no conexo se denomina grafo disconexo. Los subgrafos conexos máximos de un grafo no dirigido se llaman componentes o componentes conexos. En la teoría de grafos, la conectividad es un concepto fundamental que se relaciona con la resiliencia de una red y se puede determinar utilizando algoritmos como la búsqueda en profundidad (DFS) o búsqueda en anchura (BFS).

¿Tienes una idea?

Usa este espacio para añadir una interactividad genial. Incluye texto, imágenes, vídeos, tablas, PDFs… ¡incluso preguntas interactivas! Tip premium: Obten información de cómo interacciona tu audiencia:

• Visita las preferencias de Analytics;
• Activa el seguimiento de usuarios;
• ¡Que fluya la comunicación!

¿Tienes una idea?

Usa este espacio para añadir una interactividad genial. Incluye texto, imágenes, vídeos, tablas, PDFs… ¡incluso preguntas interactivas! Tip premium: Obten información de cómo interacciona tu audiencia:

• Visita las preferencias de Analytics;
• Activa el seguimiento de usuarios;
• ¡Que fluya la comunicación!