Tercera Unidad De Matematicas Discretas

Un grafo
Simple esta representado por una letra G y esta letra g va a tener asociados dos elementos el elemento v que es un conjunto Finito no vacio de elementos llamados vértices nodos puntos va a depender mucho de la bibliografía que ustedes consulten
Eñ otro elmento que conforma es a que es un conjunto de pares no ordenados de elementos distintos de v llamados aristas arcos
Formalmente,un grafo G consiste en dos conjuntos finitos N y A. N es el conjunto de elementos del grafo, también denominados vértices o nodos. A es el conjunto de arcos, que son las conexiones que se encargan de relacionar los nodos para formar el grafo. Los arcos también son llamados aristas o líneas.
Los nodos suelen usarse para representar objetos y los arcos para representar la relación entre ellos.Por ejemplo, los nodos pueden representar ciudades y los arcos la existencia de carreteras que las comunican.
Cada arco queda definido por un par de elementos n1, n2 ∈ N a los que conecta. Aunque habitualmente los elementos son distintos, permitiremos que sean el mismo nodo (n1 = n2).




Vamos a considerar un ejemplo

Vas a suponer quetenemos un conjunto de vértices que coniene a loselementos abcd y e
Y os representamos con un pequeño circulo donde colocamos el nombre del nodo para representar las aristas asemos una sucesión de pares ordenados en este caso tenemos los pares ordenados de a con b .d con c
Eeee qiero aser la aclaración que aki decimos par ordenados aunque en realida no es que se ordenada uno con el otro eso lo vamos a ver en el otro caso que son grafosdirigidos aki en esta grafica mostraremos que visualmente asemos una coneccion entre cada uno de los nodos solamente se conectan a través de una pequeña línea


Cuando osotros trabajamos con grafos ya en el ambiente real ya tratando de representar un modelo matemático vams a necesitar en muxxas ocasiones darles una dirección de corresponencia de entre cada uno de los nodos esa dirección genea lo quenostros conocemos como grafos dirigidos un grafo dirigido es nuevamente un para de conjuntos conjuta v de vértices conjunto a de aristas nada mas que eneste caso en especial para cada par ordenado de vértices que definen una arista el primer elemnto se le va a conocer como vértice inicial y al segundo elemnto se le conoce como vértice final el vértice final es el que nos vaa dar el sentido de larelación que va a existir entre los vértices por ejemplo vamos a tomar el grafo anterior el mismo conjunto pero ahora le vamos a dar una dirección y entoncs ahora nuestras aristan toman un sentido de par ordenado que el par ordenado el primer elemento es darle el vértice inicial a y el segundo elemnto determina el vértice final de la relación que va del elemnto a al elemento b y asi sucesivamenteesto que estamos viendo en pantalla es un grafo dirigido porque nos esta dando una dirección,






Grafo simple

Un grafo es simple si a lo más sólo 1 arista une dos vértices cualesquiera. Esto es
equivalente a decir que una arista cualquiera es el único que une dos vértices
específicos.
Un grafo que no es simple se denomina complejo.


Grafo completos
Un grafo simple es completosi 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 Kn, es decir, grafo completo de n vértices tiene exactamente, aristas.
La representación gráfica de los Kn como los vértices de un polígono regularda cuenta de su peculiar estructura.
Grafo bipartitos

Un grafo G es bipartito si puede expresarse como G = {V1 + V2, A} (es decir, la unión
de dos grupos de vértices), bajo las siguientes condiciones:

* V1 y V2 son distintos y tienen más de un elemento cada uno.
* Una arista en A une un vértice de V1 con uno de V2.
* No existen aristas uniendo dos elementos de V1; análogamente para...