Matemáticas Discretas

Universidad Autónoma de Sinaloa[pic 1][pic 2]

Facultad de Ingeniera Los Mochis                 Ingeniera en Software

                 Matemáticas Discretas

L. I Manuel de Jesús Rodríguez Guerrero

Grupo 1-02

Ramon de Jesús Ruiz Castro  

                                              Viernes 3 de diciembre del 2021

Unidad 4

Grafos

Los Grafos son estructuras discretas que constan de vértices y de aristas que conectan entre si esos vértices.

[pic 3][pic 4]

[pic 5]

Tipos de grafos

Grafos Simples:

Un grafo simple, se representa como G = (V, E), consta de V, un conjunto no vacío de vértices, de E, un conjunto de pares no ordenados de elementos distintos de V (A estos pares se les llama aristas).

Un ejemplo de un grafo simple sería el siguiente, donde los vértices representarían a los distintos ordenadores y las aristas no dirigidas representarían a las distintas líneas telefónicas de una red informática.[pic 6]

Multígrafo

Un Multígrafo, representado como G = (V, E) consta de un conjunto de V de vértices, un conjunto de E aristas y una función f de E en { {u, v} | u, v ϵ V, u != v}. Se dice que las aristas e1 y e2  son aristas múltiples o paralelas si f (e1) = f (e2).

[pic 7]

Pseudografo

Un pseudografo, representado como G = (V, E) consta de un conjunto de V vértices, un conjunto de E aristas y una función f de E en { {u, v} | u, v ϵ V}.  Una arista e es un bucle, o lazo, si f (e) = {u, u} = {u} para algún u ϵ V.        

 [pic 8]

Grafo Dirigido

Un grafo dirigido, representado como G = (V, E) consta de V de vértices y de un conjunto E de aristas, que son pares ordenados de elementos de V.

[pic 9]

Multígrafo Dirigido

Un multígrafo dirigido, representado como G = (V, E) consta de un conjunto V de vértices, un conjunto E de aristas y una función de f de E en { (u, v) | u, v ϵ V}. Se dice que las aristas e1 y e2 son aristas múltiples si f (e1) = f (e2).        

[pic 10]

Matriz de incidencia y adyacencia

La matriz de incidencia es aquella matriz que representa el gráfico de tal manera que con la ayuda de esa matriz podemos dibujar un gráfico.

[pic 11]

[pic 12]

La matriz de adyacencia es una matriz cuadrada que se utiliza como una forma de representar relaciones binarias. Se crea una matriz cero, cuyas columnas y filas representan los nodos del grafo. Por cada arista que une a dos nodos, se suma 1 al valor que hay actualmente en la ubicación correspondiente de la matriz.

[pic 13]

Ciclo de Euler y Hamilton

Ciclo de Euler: Recorre todas las aristas del grafo sin repetir ninguna.

Teorema: Sea G un grafo (finito y conexo).

(a) la suma de las valencias de todos sus vértices es par. Es decir, hay un “número par de vértices impares”.

(b) Si el número de vértices impares es mayor que dos, el grafo no se puede recorrer [sin pasar dos veces por ninguna arista].

(c) Si el número de vértices impares es cero, el grafo se puede recorrer. Podemos además elegir por qué vértice empezar, y el camino siempre será cerrado (termina donde empezó).

(d) Si el número de vértices impares es dos, el grafo se puede recorrer, pero el camino ha de empezar en uno de los dos vértices impares y terminar en el otro.
Matriz para recorrer el grafo sin repetir ningúna arista.

Ciclo de Hamilton:  W.R. Hamilton (1805-1865) inventó (y patentó) un juego en el que se trataba de hacer un recorrido por 20 ciudades (vértices) del mundo sin pasar por ninguna más de una vez. Las ciudades estaban unidas por 30 aristas, formando el grafo de un icosaedro.

Un circuito hamiltoniano, o de Hamilton, es un grafo G es un camino que comienza y termina en un mismo vértice, pasando exactamente una vez por cada vértice. 

Recorrido y camino de Euler y Hamilton

Donde Euler representa a las aristas y Hamilton a los vértices:

Se considera “Recorrido” si y solo si los vértices son 2 impares, inicia en un impar y termina en el otro impar.

Se considera “Ciclo” cuando en el grafo todos los nodos o vértices son de grado Par, entonces puede iniciar en cualquier vértice y terminar donde mismo.

Se considera “Camino” en cualquier otro caso donde no sea ni camino ni recorrido.

Arboles

Un árbol es un tipo de grafo al cual se le denomina así por el gran parecido que tienen estos grafos a los árboles.

Un árbol es un grafo no dirigido, conexo y sin ciclos.

...