MMDI U2 A1 EDSL





Matemáticas Discretas

1) Gráficas o grafos.
Un grafo es una representación gráfica de diversos puntos que se conocen como nodos o vértices, los cuales se encuentran unidos a través de líneas que reciben el nombre de aristas

Los grafos pueden ser clasificarse de diversas maneras según sus características. Los grafos simples, en este sentido, son aquellos que surgen cuando una únicaarista logra unir dos vértices. Los grafos complejos, en cambio, presentan más de una arista en unión con los vértices.

Los grafos suelen representarse mediante subconjuntos del plano, en estas llamadas representaciones graficas se usan puntos o nodos para los vértices, y líneas para las aristas. En la representación grafica cada línea debe comenzar y terminar en un nodo, esto significaque a esa arista le corresponden esos vértices.

2) Partes de un grafo.
Nodos. Se indican por medio de un pequeño círculo y se le asigna un número o una letra.

Aristas. Son las líneas que unen un nodo con otro y se les asigna una letra un número o una combinación de ambos.

Aristas paralelas. Son las aristas que tienen relación con un mismo par de nodos.

Lazo. Es aquella arista que sale de unnodo y regresa al mismo nodo.

Valencia de un nodo. Es el número de aristas que salen o entran a un nodo.

2) Clasificación de un grafo
Grafos simples. Son aquellos grafos que no tienen lazos ni aristas paralelas.

Grafo completo de orden N. Es el grafo en donde cada nodo está relacionado con todos los demás, sin lazos ni lados paralelos. Se indica Kn en donde n es el número de nodos. La valenciade cada uno de los nodos de los grafos completos está dada por la expresión:

Número de aristas= n(n-1)/2 en donde n es el numero de nodos.

Grafo bipartito completo. Es el grafo que esta compuesto por dos conjuntos de nodos, uno de ellos A={a1, a2, a3, ....., an} y otro B={b1, b2, .....,bm} y en el que cada nodo de A esta unido con todos los nodos de B, pero entre los nodos del mismo conjunto noexiste ninguna arista que los una. Se indica como Kn,m en donde n y m es el numero de nodos de cada uno de los conjuntos.

Grafo dirigido. Es el grafo en donde las aristas tienen asociadas una dirección.

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. Este grafo no tiene lazos ni ramas paralelas.

3) Teoría de grafosLa teoría de grafos estudia las propiedades de los grafos, que son colecciones de objetos llamados vértices (o nodos) conectados por líneas llamadas aristas (o arcos) que pueden tener orientación (dirección asignada). Típicamente, un grafo está diseñado por una serie de puntos (los vértices) conectados por líneas (las aristas).
LOS SIETE PUENTES DE LA ISLA KUEIPHOF. La isla Kueiphof enKoenigsberg (Pomerania) el río que la rodea se divide en dos brazos. Sobre los brazos estaban construidos siete puentes y para los habitantes era motivo de distracción descubrir un itinerario de manera que pudieran regresar al punto de partida, después de haber cruzado por los siete puentes pero pasando sólo una vez por cada uno de ellos. Leonardo Euler estudió el asunto, representó las distintaszonas A, B, C y D por medio de puntos, mientras que los puentes estaban representados por líneas que unían estos puntos. A la figura la llamó grafo, a los puntos los llamó vértices y a las líneas las denominó aristas. Estudió si una figura lineal se podía dibujar con un solo trazo, sin levantar el lápiz del papel y sin pasar dos veces por el mismo sitio.
1. Imposible si hay más de dos vérticesimpares.
2. Es posible cuando: a) Todos los vértices son pares y el punto de partida puede ser cualquiera. b) Cuando no hay más de dos vértices impares y en este caso el comienzo del recorrido comienza en uno de ellos y termina en el otro. (Impar es un vértice si de él parten un número impar de caminos). A la isla A llegan 5 puentes; a la B llegan 3 puentes; a la orilla C llegan 3 puentes y a la...