Valor: borrador

Dos

a

b

c

d

e

Intento de redefiniciones PREVIO

Fuente:Matemáticas Discreta y CombinatoriaRalph GrimaldiTema de seminario de investigación.

Valor de borrador

Incorporación de: ....(b;b)!.......GÆ

.....(b;b)__

.....G_

.......... G.. ........

Definición 1

Sea N un conjunto no vacío y NxN † A, entonces GÆ

: {N;A} se denomina grafo dirigido. N es unconjunto de nodos y A es un conjunto de arcos.Cuando no interesa la dirección de los arcos, se denominan aristas y el grafo es no dirigido.Se

anotará: G_

: {V;A}

Dada (i;j)__

se dice que la arista es incidente en los vértices i y j. Y que los vértices i y j sonadyacentes.

Dada (m;n)Æ

se dice que n es adyacente desde m. Además m se denomina: orígen o fuente y ntérmino o destino.Si un vértice no participa de ninguna arista se denomina aislado.

Una arista del tipo (a;a)__

se llama lazo. Un arco del tipo (b;b)Æ

se llama bucle.Si no tiene lazos se llama sin lazos (*).......En general si no interesa que el grafo se dirigido o no se denomina G.

Definición 2

Sea G_

. Para x,y ΠV, se dice que hay una cadena en G_

de x a y , si existe una sucesión finita,no vacía de aristas distintas de A que une a x con y.Cuando x = y la cadena se denomina cicloUna cadena es simple cuando pasa una sola vez por cada vértice. El número de aristas indicala longitud de la cadena o ciclo. Cuando se pasa una sola vez por cada vértice se denominasimple(*)

Para GÆ

se define de manera análoga camino y circuito.

Definición 3

Sea G_

. G se denomina conexo si existe un camino que una dos vértices cualesquiera de G.Un G que no sea conexo se denomina no conexo (inconexo).

Dado GÆ

se obtiene su grafo asociado G.. ignorado la dirección de sus arcos.

Sea GÆ

. Si su grafo asociado es conexo entonces también lo es.

Valor: borrador

Si G se compone de partes que son conexas, estas se denominan componentes. Un G sedenomina conexo si y solo si tiene solamente una componente conexa.T1En todo G conexo existe un camino simple que une dos cualquiera de sus vértices.

Definición 4Sea G . Se denomina multigrafo se existe mas de una arista para algún par de vértices (a;b)para a≠b. Si estas aristas se repiten n veces la arista tiene multiplicidad n.Un multigrafo se denomina n-grafo dirigido(no dirigido), siendo n el factor de la arista demayor multiplicidad.

Definición 5Sea G . Entonces G' :{V';A'} es un subgrafo de de G, y V'† V y A'† A. Donde cada arista de A' esincidente con vértices de V'. Si G'≠G se denomina subgrafo impropio.

Definición 6

Sea G_

de n vértices , sin lazos y donde para cualquier (vi; vj ) Œ V existe una arista ( vi;vj )____

,(i≠j)entonces se denomina grafo completo y se anota Kn.

Definición 7

Sea G_

, sin lazos con n vértices. El complemento de G_

, es el grafo formado por los vértices

de G_

y las aristas que no están en G_

. (Si G_

= Kn, G_

es un grafo formado por n vértices,sin aristas y se denomina grafo nulo(*)).

Definición 8Sea G1:{V1;A1} y G2: {V2;A2}, dos grafos no dirigidos. Una función f: V1 -> V2, se denominaisomorfismo de grafos si : a) si f es uno a uno y suprayectiva, y b) para todo a,b Œ V1, (a;b)Œ A1 si y solo si (f(a);f(b))Œ A2Cuando existe dicha fución, G1 y G2se denominan isomorfos

Definición 9Sea G un grafo o multigrafo no dirigido. Para cualquier vértice de G, el grado de v (grad(v),es el número de aristas de G incidentes con v.T2.Si G = {V;A} es un grafo o multigrafo no dirigido, entonces S grad(v) = 2ACorolario 1Si G = {V;A} es un grafo o multigrafo no dirigido, el número de vértices de grado impar debeser par.

Definición 10Si G = {V;A} es un grafo o multigrafo no dirigido, Se dice que G tiene un ciclo de Euler s iexiste un ciclo en G que pase por todo v y por toda a una solo vez. Si hay un camino de a a b yeste pasa por cada v y cada a una sola vez, se llama camino de Euler.T3.Si G = {V;A} es un grafo o multigrafo no dirigido, entonces G tiene un camino de Euler si ysolo si G es conexo y todo v tiene grado par.CorolarioSi G = {V;A} es un grafo o multigrafo no dirigido, se puede construir un camino de Euler si ysolo si G es conexo y tiene sólo dos vértices d grado par.

Definición 11Un grafo G se denomina plano si G se puede dibujar en el plano con sus aristas intersecándosesolamente en los vértices de G.(*realizables)

Valor: borrador

Definición 12Un grafo G se denomina bipartito si V= V1 ª V2 con V1 ´ V2 = vacío y cada arista tiene unvértice en V1 y otro en V2. Si cada vértice de V1 está unido con uno de V2 se tiene un grafobipartito completo. Cuando V2 =m, V2 el grafo se anota como Km,nK se denomina grafo de servicios.

Definición 13Si G1:{V1;A1} y G2: {V2;A2} entonces se denominan homeomorfos, si G2 se puede obtener apartir de la inserción o eliminación de vértices de grado 2.T4 ( de Kuratowski)Un grafo es plano si y solo si contiene un subgrafo homeomorfo a K5 o K3,3.T5Sea G un grafo plano conexo con V= vA. Sea r el número de regiones del plano determinadaspor G, una de éstas tiene un área infinita y se denomina región infinita. Entonces, v -a +r =2C3Sea G un grafo plano conexo sin lazos con V =v, A = a > 2, y r regiones. Entonces 3r =< 2a ya=< 3v -6

Definición 14Sea G un grafo o multigrafo no dirgido. Un subconjunto A' de A se denomina conjunto de cortede G si eliminando las aristas de A' de G, se incrementa el número de componentes de G, y noes posible lograrlo con ningún subconjunto propio de A'

Definición 15Si G s un grafo o multigrafo se dice que G tiene un ciclo de Hamilton si existe u ciclo simplede G que contenga todo vértice de de v. Un camino de Hamilton es un camino simple de G quecontiene todos los vértices.Sugerencias:1 Si G tiene un ciclo de Hamilton entonces, v pert V, grad(v) >= 22 Si a pert a V grad(a) = 2, entonces las dos aristas incidentes co el vértice a debe apareceren cualquier ciclo de Hamilton de G3 Si a pert a V grad(a) > 2, entonces cuando se intenta construir un ciclo de Hamilton, unavez que se pase por a, las aristas no utilizadas incidentes con a se dejan de tener en cuenta.4 Construyendo un ciclo de Hamilton para G, no se puede obtener un ciclo simple para unsubgrafo de G, a menos que contenga todos los vértices de G.T6.Sea.K*n un grafo dirigido completo; es decir K*n tiene n vértices y para cualquier par devértices distintos x,y, al menos la arista xy o yx está en K*n. Dicho grafo siempre contieneun ciclo de Hamilton.T7Sea G u grafo sin lazos con v = n. Si grad(v) +grad(y) >= n -1 para todo xy pert V, x≠y,entonces G tiene un camino de Hamilton.C4Sea G un grafo sin lazos con n vértices. Si grad(v) >= (n -1)/2 para v pert a V, entoncestiene un camino de Hamilton.

Definición 16Si G es un grafo no dirigido, aparece una coloración apropiada de G cuando se colorean losvértices de G de todo que si ab es arista de G, entoces a y b se pintan de colores distintos. Deahí qué vértices adyacentes tengan colores distintos. El número de colores necesarios paracolorear de esta forma a G se denomina número cromático de G y se nota lambda¥(G)XXSi G es un camino simple de n vértices entonces P(G,¥) = ¥(¥-1)^(n-1)T8De descomposición para polinomios cromáticos

Valor: borrador

Si G es conexo y a pert A entonces P(Ga,¥) = P(G,¥) +P(G'a,¥)T9Para cualquier grafo G, el término constante de P(G,¥) = 0T10T11T12

Arboles

Definición 1Sea G un grafo o dirigido. G se denomina árbol si es conexo y sin ciclosBosque conjunto de arbolesUn subgrafo de G que contenga todos sus vértices y sea una árbol se llama árbol abarcadorT1Si a y b son vértices de R entonces hay un camino que los conectaT2Si G es un grafo o dirigido entonces es conexo sii tiene árbol abarcador.T3En cualquier R, V= A+1DefiniciónVértice de grado 1: Vértice colganteT4Si en R V>=2 entonces tiene al menos dos vértices colgantes