ACTIVIDAD UNIDAD 2
GRAFOS COMPLETOS
En el campo matemático de la teoría de grafos, un grafo completo es un grafo
simple no dirigido en el que cada par de vértices distintos está conectado por
una única arista. Un dígrafo completo es un grafo dirigido en el que cada par
de vértices distintos está conectado por un par de aristas únicas (una en cada
dirección).
La teoría de grafos en sí misma suele fecharse a partir del trabajo de 1736 de
Leonhard Euler sobre los Siete puentes de Königsberg. Sin embargo, los
dibujos de grafos completos, con sus vértices colocados sobre los puntos de un
polígono regular, aparecieron ya en el siglo XIII, en la obra de Ramon Llull.
Este dibujo a veces se denomina rosa mística.
GRAFOS REGULARES
En Teoría de grafos, un Grafo regular es un grafo donde cada vértice tiene el
mismo grado o valencia. Un Grafo regular con vértices de grado k es llamado
Grafo k-regular o Grafo regular de grado k.
Los Grafos regulares de grado hasta 2 son fáciles de clasificar: Un grafo 0-
regular consiste en un grafo con vértices desconectados, un grafo 1-regular
consiste en un grafo con aristas desconectadas, y un grafo 2-regular consiste
en un ciclo.
Un grafo 3-regular es conocido como un grafo cubo.
Un grafo completo Kn es (n-1)-regular
GRAFOS BIPARTITOS
Los grafos bipartitos suelen representarse gráficamente con dos columnas (o
filas) de vértices y las aristas uniendo vértices de columnas (o filas) diferentes.
Los dos conjuntos U y V pueden ser pensados como un coloreo del grafo con
dos colores: si pintamos los vértices en U de azul y los vértices de V de verde
obtenemos un grafo de dos colores donde cada arista tiene un vértice azul y el
otro verde. Por otro lado, si un grafo no tiene la propiedad de que se puede
colorear con dos colores no es bipartito. Un grafo bipartito con la partición de
los vértices en U y V suele denotarse G = (U, V, E). Si |U| =|V|, esto es, si los
dos subconjuntos tienen la misma cantidad de elementos o cardinalidad,
decimos que el grafo bipartito G es balanceado. Si todos los vértices del
mismo lado de la bipartición tienen el mismo grado, entonces G es llamado
grafo birregular.
GRAFOS PLANOS, TEOREMA
En teoría de grafos, un grafo plano (o planar según referencias) es un grafo
que puede ser dibujado en el plano sin que ninguna arista se cruce (una
definición más formal puede ser que este grafo pueda ser "incrustado" en un
plano). Los grafos K5 y el K3,3 son los grafos no planos minimales, lo cual
nos permitirán caracterizar el resto de los grafos no planos.
Todo grafo plano puede ser dibujado sobre la esfera, y viceversa. Una
generalización de los grafos planos son grafos dibujados e incrustados sobre
superficies de género arbitrario. En esta terminología, los grafos planos tienen
género 0, por ser el plano y la esfera de género 0.
Teorema de Kuratowski
Un grafo es plano si y solo si no contiene un subgrafo isomorfo a una
subdivisión elemental de K5 (el grafo completo de 5 vértices) o K3,3 (el grafo
bipartito completo de 6 vértices).
GRAFOS ÁRBOLES, TEOREMAS, PROPIEDADES
En teoría de grafos, un árbol es un grafo en el que cualquier par de vértices
están conectados por exactamente un camino, o alternativamente, es un grafo
conexo acíclico. Un bosque es un grafo disconexo acíclico. Alternativamente,
se puede definir como una unión disjunta de árboles, es decir, es un grafo
disconexo cuyas componentes son árboles.
GRAFOS DIRIGIDOS
Un grafo dirigido o digrafo es un tipo de grafo en el cual las aristas tienen un
sentido definido,1 a diferencia del grafo no dirigido, en el cual las aristas son
relaciones simétricas y no apuntan en ningún sentido.
A veces un digrafo es denominado digrafo simple para distinguirlo del caso
general del multigrafo dirigido, donde los arcos constituyen un multiconjunto,
en lugar de un conjunto. En este caso, puede haber más de un arco que unos
dos vértices en la misma dirección, distinguiéndose entre sí por su identidad,
por su tipo (por ejemplo, un tipo de arco representa relaciones de amistad
mientras que el otro tipo representa mensajes enviados recientemente entre los
nodos), o por un atributo como por ejemplo su importancia o peso. A menudo
también se considera que en un digrafo simple no están permitidos los bucles.
DÍGRAFOS Y RELACIONES
Si A es un conjunto finito y R es una aplicación sobre A, también se puede
representar R gráficamente como sigue. Se traza un círculo para cada
elemento de A y se marca el círculo con el elemento correspondiente de A. A
estos círculos se los llama vértices. Se traza a continuación una flecha, a la
flecha se le llama lado o arco, del vértice ai al vértice aj si y solamente sí ai R
aj. La representación gráfica resultante de R se llama gráfica dirigida o dígrafo
de R.
CONJUNTOS QUE SURGEN DE LAS RELACIONES
Sea , una relación de A a B. Se va a definir ahora varios conjuntos
importantes y útiles relacionados con R.
El dominio de R, denotado Dom(R), es el conjunto de todos los elementos de
A que están relacionados con algún elemento de B. En otras palabras,
Dom(R), un subconjunto de A, es el conjunto de todos los primeros elementos
de los pares que forman R. De modo similar, se define el rango de R,
designado por Ran(R), como el conjunto de todos los elementos de B que
están relacionados con algún elemento de A.
Los elementos de A que no están en Dom(R) no están involucrados en la
relación R de manera alguna. Esto es cierto también para los elementos de B
que no están en el rango de R.
DÍGRAFOS Y MATRICES
Un grafo es una representación gráfica de un conjunto de objetos llamados
vértices, unidos por enlaces que llamamos aristas, con el fin de expresar una
relación binaria entre los elementos del conjunto.
La matriz de adyacencia es la matriz en la que los vértices se ordenan en las
filas y columnas y cada elemento representa el número de aristas que unen el
vértice de la fila con el vértice de la columna .
Para crear la matriz de adyacencia podemos seguir los siguientes pasos:
Rellenamos, elemento a elemento, empezando por el de la primera fila con la
primera columna. Esto significa si entre el vértice y el vértice hay alguna
conexión (arista).
Si hay una conexión, se pone un .
Si no hay ninguna conexión, se pone un .
La matriz de incidencia relaciona los vértices con las aristas.
Hay muchos tipos de grafos, en función de sus características. Por ejemplo:
grafos no dirigidos, grafos dirigidos, grafos simples, multigrafos, grafos
conexos, etc.
Los grafos son objetos que se pueden aplicar a muchas ramas científicas,
como la sociometría, la antropología, la comunicación, la geografía, las redes
sociales, entre muchas otras.
DÍGRAFOS CONEXOS
En teoría de grafos, un grafo conexo o conectado1 es un grafo en que todos
sus vértices están conectados por un camino (si el grafo es no dirigido)2 o por
un semicamino (si el grafo es dirigido). Un grafo que no es conexo se
denomina grafo disconexo o inconexo. Los subgrafos conexos máximos de un
grafo no dirigido se llaman componentes o componentes conexos.1 Para el
caso de los grafos dirigidos, si no se considera el sentido de las aristas, se
habla de componente débilmente conexo, mientras que sí se considera el
sentido, se habla de componente fuertemente conexo.
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 tiene vértices de corte,
esto es, vértices tales que al quitarlos el grafo resultante se vuelve disconexo.
En ciencias de la computación, es posible determinar si un grafo es conexo
usando un algoritmo de 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 estos 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.
