Hola buenas hoy me toca currar doble ya que he ido dejando esto para más tarde y me he juntado con que tengo que hacer 2 entradas hoy y mañana tenemos clase de mates osea que mañana me tocará hacer otra, bueno voy a ver de lo que me acuerdo ayudandome de los apuntes y a ver que sale, espero que bien jejeje.
Sesión correspondiente al día (16/11/2010).
En esta sesión hemos continuado el tema de los grafos.
-
Tipos de grafos
·Grafo no dirigido asociado: es un grafo dirigido a un grafo con el mismo conjunto de vértices y en el que se han ognorado las direcciones de los vértices.
·Grafo mixto: contiene tantos arcos como aristas, es decir, contiene ambas cosas.
·Grafo simple:
1-No dirigido= sin bucles y no hay dos aristas que unan el mismo par de vértices.
2-Dirigidos= sin bucles y no hay dos arcos uniendo el mismo par de vértices y con la misma dirección.
Si un grafo no es simple se llama multigrafo.
No es simple ya que tenemos un bucle y dos aristas con la misma dirección uniendo los mismos vértices.
Este sí es simple porque aunque tiene 2 aristas, son de distinta dirección.
·Grafo no dirigido completo: si hay al menos una arista (arco) uniendo cada par de vértices distintos.
Si estos grafos son simples se denominan kn.
-kn= grafos completos no dirigidos y simples con “n” vértices.
Ejemplo:
-
Contar aristas de un grafo
Vamos vértice a vértice uniendo con los que todavía no están unidos. Al final los sumamos.
Una vez tenemos el número de vértices y de aristas se hace lo siguiente: (vértices * aristas)/2 = aristas del grafo completo
Para los grafos kn hacemos |A|= (n*(n-1))/2
-
Determinar el número crómatico de un grafo, grafos bipartidos y grafo km,n
Se parte el grafo en dos formando un grafo bipartido.
·Grafo bipartido: fromado por dos conjuntos de vértices {V1, V2}
-Los vértices de ambos conjuntos han de estar conectados entre sí pero los de V1 no lo estarán entre ellos y tampoco lo estarán los de V2.
-La unión de ambos dará el conjunto completo.
-Su intersección dará el conjunto vacío.
Ejemplo:
V1={x, t}
V2={z, y}
En este grafo es sencillo distinguir los dos grupos de vértices pero en un grafo más complejo no es tan sencillo. En estos casos debemos seguir el siguiente procedimiento:
1-Elegimos un vértice cualquiera.
2-Ponemos una etiquieta a ese vértice y una distinta para los vértices conectados a él, esta etiquieta es distinta al vértice elegido pero común para los vértices conectados a él.
Ejemplo:
En este caso hemos empezado etiquetando el vértice “2″ con un 2 y los vértices adyacentes con un “1″, después el vértice que no es adyacente lo hemos vuelto a etiquetar con un “2″ y sus adyacentes con un “1″.
Una vez hecho esto tendremos un conjunto formado por los vértices con la etiquieta “1″ y otro formado por la etiquieta “2″.
V1={0, 1, 3, 4, 6, 7}
V2={2, 5}
Ahora se sabe cuántos colores son necesarios para pintar este grafo. Con dos colores será suficiente ya que la única condición para pintarlos es que no hayan dos grafos adyacentes pintados iguales y gracias a esta distinción de conjuntos se puede cumplir dicha condición.
Para los grafos dirigidos se hará con su grafo asociado (para comprobar si es bipartido).
También se puede tener grafos bipartidos completos si cada vértice de V1 está unido con vada vértice de V2.
·km,n: grafo no dirigido bipartido completo y simple con card(V1)=m, card(V2)=n.
Subgrafo y grafo generador
·Subgrafo: si tenemos un grafo G= (V, A) y un grafo H=(V’, A’). H es subgrafo de G si el número de vértices y aristas de H es menor o igual al de G.
Ejemplo:
También sería un subgrafo un único vértice (sin aristas) o el propio grafo. Si se cumple que el número de vértices del subgrafo es menor o igual al número de vértices del grafo original y que el número de aristas del subgrafo es menor o igual que el número de aristas del grafo original, entonces se trata de un subgrafo.
·Grafo generador: un subgrafo es generador si V(G)=V(H).
Todo grafo tiene un subgrafo generador simple.
Si el grafo G tiene el mismo número de vértices que el grafo H, entonces H es un subgrafo generador simple, siempre respetando el número de aristas para que sea un subgrafo, es decir, que el número de aristas de H sea menor o igual que el número de aristas de G.
H1 es un subgrafo ya que cumple todo lo comentado y además es generador porque tiene el mismo número de vértices que G1. También es simple.
-
Grado de un vértice de un grafo no dirigido y de un grafo dirigido
·Grado de un vértice de un grafo no dirigido:
dG(v): número de aristas incidentes con él (número de aristas que lo tienen como extremo). Cada bucle se cuenta dos veces.
Γ(v): conjunto de vértices adyacentes a V.
·Grado de un vértice de un grafo dirigido: Se cuentan arcos de entrada y salida y el grado total es la suma de ambos.
Y hasta aqui vimos ahora voy con lo de la siguiente semana!!!