Camino Hamiltoniano

SedefinecomoCaminoHamiltonianoauncaminocualquiera,quepasapor todoslosverticesdeungrafo,unasolavez(sincircuitors).Puedeempezar desde cualquier vertice yterminarencualquierotro.EsquemaBacktrackingde una solucion. proc CamHam( Grafo: g; Vertice: v; Ref Lista: Sol; Logico: enc ) var

Lista: suc Vertice: vact

inicio suc ← g.sucesores( v ) mientras ( ¬suc.EsVacia() ∧ ¬enc ) hacer

vact ← suc.Consultar( 1 ) suc.Eliminar( 1 ) si ( ¬Sol.Esta( vact ) ) entonces

Sol.Insertar( vact, Sol.Longitud() + 1 ) si ( Sol.Longitud() = g.nVertices() ) entonces //Basta con

enc ← verdadero //comprobar longitud porque en Sol sino //no hay vertices repetidos

CamHam( g, vact, Sol, enc ) fsi

fsi si ( ¬enc ) entonces

Sol.Eliminar( visitados.Longitud() + 1 ) fsi

fmientras fproc

Llamamos al proc CamHam() desde cada vertice, hasta encontrar una

solución. proc CaminoHamiltoniano( Grafo: g; Vertice: v; Lista: camham ) var

Logico: flag Lista: vertices

inicio enc ← falso suc.construir() vertices ← g.Vertices() mientras ( ¬vertices.EsVacia() ∧ ¬enc ) hacer

//El camino empieza en el vertice origen camham.Insertar( vertices.Consultar( 1 ), 1 ) CamHam( g, vertices.Consultar( 1 ), camham, enc ) vertices.Eliminar(1) //Si no encontro la sol elimino el vertice origen //que inserte antes de CamHam() si ( ¬enc ) entonces

camham.Vaciar() fsi

fmientras ffunc

Grafo Bicoloreable

Un grafo es bicoloreable si se puede asignar colores (elegidos de una

paletadedoscolores)acadavérticedemaneratalquedosvérticesadyacentes notenganelmismocolor.Esdecirelgrafosepuedecolorearusandosolodos colores.

Observaciones: 1. El grafo no tiene bucles. 2. El grafo es no dirigido. 3. El grafo es conexo. 4. No utilice apuntadores en su solución. 5. El algoritmo debe ser a lo sumo O(V + E). func EsBicoloreable( Grafo: g ): Lógico var

Logico: flag Entetro: i Arreglo[1...n] de Cadenas: Color //n = g.Orden Cola: C Lista: L,Vert Vertice: u,v

inicio para i ← 1 hasta g.Orden() hacer

Color[i] ← "blanco"//El orden de un grafo es la cantidad de //vertices

fpara Vert ← g.Vertices(); Color[ Vert.Consultar( 1 ) ] ← "gris" C.Encolar( Vert.Consultar( 1 ) ) flag ← verdadero

// Como el grafo es conexo podemos empezar a recorrerlo desde //cualquier vertice, por ejemplo el primero de la lista, y //pintarlo de cualquier color e ir pintando sus sucesores

//Recorrido BFS mientras ( ¬C.EsVacia() ∧ flag ) hacer

u ← C.Frente() C.Desencolar() L ← g.Sucesores( u ) mientras ( ¬L.EsVacia() ) hacer

v ← L.Consultar( 1 ) L.Eliminar( 1 ) si ( Color[ v ] ← "blanco" ) entonces // Si no aún no está pintado, lo pintamos de un color// diferente al U ( al vertice actual ) y lo encolamos

si ( Color[ u ] = "gris" ) entonces Color[ v ] ← "negro"

sino Color[ v ] ← "gris"

fsi C.Encolar( v )

sino // Si ya esta pintado, debe tener un color diferente al // vertice actual, si son del mismo color entonces se // necesitan mas de dos colores y ya no es bicoloreable

si ( Color[ v ] = Color[ u ] ) entonces flag ← falso

fsi fsi

fmientras fmientras

retornar ( flag )

ffunc

Sol con Apuntadores y de otra manera func Grafo::EsBicoloreable(): Lógico var

Logico: flag Entetro: colAdy, i Arreglo[1...n] de Enteros: Color //n = instancia.n(cantidad de vertices) Apuntador a NodoA: Vact, Velim Apuntador a NodoV: Aact,Aelim

inicio para i ← 1 hasta instancia.n hacer

Color[i] ← 0 //Sin color fpara flag ← verdadero Vact ← instancia.g mientras ( flag ∧ Vact != nulo ) hacer

si ( Color[ Vact↑.ObtInfo() ] = 0 ) entonces Color[ Vact↑.ObtInfo()← 1 //Si no tiene color, lo pinto de 1 // Como el grafo es no dirigido, si el no ha sido pintado es // porque sus adyacentes tampoco, por eso ninguno de sus // adyacentes deberia tener color 1 (ni 2), porque aun no // han sido pintados.

fsi si ( Color[ Vact↑.ObtInfo() ] = 1 ) entonces

colAdy ← 2 //Si el vertice actual es de color 1 los adyacentes deben //ser de color 2

sino colAdy ← 1 //Sino al revez

fsi Aact ← Vact.pri //Ahora se pintan los adyacentes mientras ( flag ∧ Aact != nulo ) hacer

si ( Color[ Aact↑.ObtVertice()↑.ObtInfo() ] = 0 ) entonces

Color[ Aact↑.ObtVertice()↑.ObtInfo() ] ← colAdy //Si no tiene color, lo pinto del que debe llevar

sino flag ← Color[ Aact↑.ObtVertice()↑.ObtInfo() ] = colAdy //Y si tiene comprueba que sea el que debe llevar

fsi Aact ← Aact.ObtSig()

fmientras Vact ← Vact.ObtSig()

fmientras retornar (flag)

ffunc

Orden de Precedencia de un Vertice

LongituddelcaminomaslargodesdeunafuentehastaelverticeV.Buscamosel caminomaslargodesdecadafuentealverticeVyguardamoslalongituddelmas largo. func ordenPrecedencial(Grafo: g, Vertice: v): entero var

Entero: nlargo Lista: fuentes, Sol,caminoAct

inicio nlargo ← 0 fuentes ← g.fuentes() Sol.construir() caminoAct.construir() mientras( ¬fuentes.EsVacia() )hacer

Sol.Insertar( fuentes(1), 1 ) ordenPrecedencia(g, fuentes(1), v, Sol, caminoAct) si ( Sol.Longitud() > nlargo ) entonces

nlargo ← Sol.Longitud() fsi Sol.Vaciar() fuentes.Eliminar(1)

fmientras retornar (nlargo)

ffunc proc CamLargo( Grafo: g; Vertice: o, d; Ref Lista: Sol; Lista: caminoAct) var

Lista: suc Vertice: vact

inicio suc.construit() suc ← g.sucesores( o )

mientras ( ¬suc.EsVacia() ) hacer vact ← suc.Consultar( 1 ) suc.Eliminar( 1 ) si ( ¬caminoAct.Esta( vact ) ) entonces

caminoAct.Insertar( vact, caminoAct.Longitud() + 1 ) si ( vact = d ) entonces

si ( caminoAct.Longitud() > Sol.Logitud() ) entonces Sol ← CaminoAct

fsi sino

CamLargo( g, vact, Sol, caminoAct ) fsi caminoAct.Eliminar( caminoAct.Longitud() + 1 )

fsi fmientras

fproc

Eliminar un Vertice

Se debe eliminar el nodo del vertice, su lista de adyacencia ( nodos arcos que salen de él ) y todos los arcos de que apuntan a él ( que están en las listas de adyacencia de los demas vertices ). proc Grafo::Grado( Vertice: v) var

Apuntador a NodoA: Vact, Velim Apuntador a NodoV: Aact,Aelim

inicio Vact ← instancia.g si ( Vact↑.obtInfo() = v ) //Si el vertice v esta en la primera

Velim ← Vact //posicion Vact ← Vact↑.ObtSig() Liberar( Velim ) instancia.n ← instancia.n ­ 1

fsi mientras ( Vact = nulo )hacer

Aact ← Vact↑.obtPri() si ( Vact↑.obtInfo() = v ) entonces

mientras ( Aact ≠ nulo ) hacer Aelim ← Aact Aact ← Aact↑.ObtSig() Liberar( Aelim ) instancia.a ← instancia.a ­ 1

fmientras Velim ← Vact Vact ← Vact↑.ObtSig() //Siguiente vertice Liberar( Velim ) instancia.n ← instancia.n ­ 1

sino si ( Aact != nulo ) entonces //Si el vertice act tiene

Aelim ← nulo //arcos si ( Aact↑.obtVert()↑.obtInfo() = v ) //Si el arco que

Vact↑.pri ← Aact↑.ObtSig() //apunta a v es Aelim ← Aact // el primero

fsi mientras ( Aact != nulo ∧ Aelim = nulo ∧ Aact↑.Obtsig()↑.obtVert() != nulo ) hacer si ( Aact↑.Obtsig()↑.obtVert()↑.obtInfo() = e ) entonces

Aelim← Aact↑.ObtSig() Aact.sig ← Aelim↑.ObtSig() fsi

fmientras si ( Aelim != nulo ) entonces

Liberar( Aelim ) instancia.a ← instancia.a ­ 1

fsi fsi Vact ← Vact↑.ObtSig() //Siguiente vertice

fsi fmientras

fproc

Camino mas largo desde un Vertice V ( Cualquier Destino )

Dado un vertice V encontrar el camino mas largo sin ciclos (sin

circuitors)partiendoconél.Esigualqueencontrarelcaminomaslargodeun verticeVaunverticeUperoenestecasoU(eldestino)noseespecifica, el camino puede terminar en cualquier vertice. proc CamLargoCD( Grafo: g; Vertice: v; Ref Lista: Sol; Lista: caminoAct) var

Lista: suc Vertice: vact

inicio suc ← g.sucesores( v ) mientras ( ¬suc.EsVacia() ) hacer

vact ← suc.Consultar( 1 ) suc.Eliminar( 1 ) si ( ¬caminoAct.Esta( vact ) ) entonces

caminoAct.Insertar( vact, caminoAct.Longitud() + 1 ) si ( EsSol( g, act, caminoAct ) ) entonces //EsSol función

magica si ( caminoAct.Longitud() > Sol.Logitud() ) entonces

Sol ← CaminoAct fsi

sino CamLargoCD( g, vact, Sol, caminoAct )

fsi caminoAct.Eliminar( visitados.Longitud() + 1 )

fsi fmientras

fproc

Es Solucion si todos los sucesores el vertice actual ya fueron visitados o si no tiene sucesores. Si al menos uno de sus sucesores no ha sido visitado, entonces no Es Solucion y continuamos construyendo el camino. func EsSol( Grafo: g; Vertice: v; Lista: caminoAct ): Lógico var

Logico: flag Lista: suc

inicio flag ← verdadero suc ← g.sucesores( v ) mientras ( flag ∧ ¬suc.EsVacia() ) hacer

flag ← caminoAct.Esta( suc.Consultar(1)) //Si un sucesor de V no está en caminoAct (retorna falso) es porque no ha sido visitado suc.Eliminar(1)

fmientras retornar (flag)

ffunc