A continuación verás la implementación en C# del método Inserta(a, index, valor) que asigna el valor x en la posición index del array a, pero hay un detalle, y es que tenemos que desplazar los elementos a partir de la posición i en adelante. En este caso el elemento que esté en la última posición del array será eliminado, ya que en C#, el tamaño del array es fijo (no crece automáticamente como en otros lenguajes como Javascript) y no podemos insertar elementos en una posición negativa o que sea mayor que a.Length-1, que devuelve el tamaño del array – 1, ya que el primer índice del array es 0.

Código en C#:

public static void Inserta (int[] a, int index, int valor){
	if(index>=0 && index< a.Length){
              for(int i = a.Length-1; i>index; i--)
		  a[i]=a[i-1];
	      a[index] = valor;
	}
	else throw new Exception("Posición no válida");
}

Si tienen alguna duda o alguna otra implementación de este método, en los comentarios por favor.

Entradas relacionadas

El principal motivo de este post no es que aprendan CSS, sino mostrarles algunos consejos y sugerencias a tener en cuenta cuando se diseña con CSS, porque créanlo o no, todo el mundo tiene algo que decir sobre CSS.

1. La página debe ser usable y legible sin el CSS, teniendo en cuenta que es así como la ven los buscadores y muchos usuarios que usan navegadores de texto, o que no renderizan CSS.

2. Las propiedades (clases o capas) se escriben en minúsculas y sin caracteres especiales, utiliza clases cuando sea algún elemento de la página que se repite más de una vez, por ejemplo, si tienes este código HTML:

Código HTML:

<div id="destacado">
    <h2>Texto Destacado </h2>
    <p> Este es un texto destacado, pero solo habrá uno</p>
</div> 
<p class="noticia">Esto es otra noticia dentro de la página</p>
<p class="noticia">Esta es la tercera noticia, que se repite</p>
<p class="noticia">Y esta es la cuarta noticia</p>

Código CSS:

#destacado {
   color: red;
   font-weight: bold;
}
#destacado h2 {
   font-size: 1.4em;
   font-family: georgia, tahoma, serif;
}
.noticia {
   color: grey;
   font-size: .9em;
}

3. Tabula bien todas las clases, y comenta los bloques por secciones, un ejemplo de una clase sería algo como:

.myclass {
       padding: 4px 20px;
       margin-left: 5px;
       text-decoration: none;
       font-weight: bold;
}

4. La mejor forma de enlazar un archivo .css desde el .html es poniendo la siguiente línea entre las etiquetas “head” del código fuente:

<link rel='stylesheet' href='style.css' type='text/css' media='screen' />

5. Cuando definas alguna familia de letras, añade al final algun tipo de letra genérico, como serif, sans-serif, cursive, o monospace y no hace falta que estén entre comillas. Por ejemplo:

 font-family: helvetica, arial, sans-serif

6. Sobre el tamaño de la letra, algunos dicen que es mejor definirlas en % o em debido a que IE no permitía hacer zoom a las letras cuando estaban definidas en pixeles, pero últimamente he leído que es mejor en pixeles.

7. El objetivo de utilizar un reset.css es el de reducir inconsistencias de navegación en cosas como la altura de las líneas por defecto, los márgenes y el tamaño de las fuentes. El razonamiento general fue discutido en un post de Eric Meyer hace unos años. Yo personalmente utilizo el reset.css desarrollado por el mismo Meyer, aunque existen muchas versiones, pero esta es la más genérica y simple.

8. Utiliza algún IDE potente y olvídate de la vista previa en modo de diseño al estilo Dreamweaver. Ya cuando estás escribiendo código HTML y CSS tienes que hacerlo con una idea básica. Yo personalmente uso Aptana Studio , que es un IDE para desarrollo web súper profesional y gratis, con autocompletado en CSS y HTML, corrección de código, por no mencionar que permite crear proyectos usando JavaScript, PHP y Ruby on Rails.

9. Hay algunas técnicas y patrones de diseño que pueden ayudarte a reducir la cantidad de archivos de imágenes y recursos que uses para construir tu página: CSS Sliding Doors , CSS Sprites , etc. Siempre es bueno conocer este tipo de hacks.

10. Es importante también últimamente mantener y preparar la hoja de estilos para impresión y dispositivos móviles, que son una importante fuente de visitas en muchos casos.

11. Si validas tu código a medida que editas tu CSS, te evitarás muchos dolores de cabeza al final del proceso. De igual forma, asegúrate de que esa propiedad que estás utilizando esté disponible en la mayoría de los navegadores, y si vas a usar alguna de las nuevas, por ejemplo text-shadow, tienes que hacer algo como esto:

text-shadow: 1px 1px 1px #000;
-webkit-text-shadow: 1px 1px 1px #000;
-moz-text-shadow: 1px 1px 1px #000;

12. Y si quieres seguir leyendo sobre CSS, TripwireMagazine ha creado una recopilación de la mayor lista de recursos para CSS jamás mostrada. En ella se enumeran más de 155 recursos hacks y tutoriales.

No hay entradas relacionadas.

Algoritmo

1. Buscamos los dos primeros caracteres que coincidan
2. A partir de esa posicion recorremos la palabra hasta ver si coincide completamente
3. Si no coinciden, volvemos al paso 1

Código en C#

public static bool Contiene(string palabra, string cadena)
{
	for (int i = 0; i <= palabra.Length-cadena.Length; i++)
		//Si encontramos dos letras iguales
		if(palabra[i]==cadena[0])
		{
			bool contenida = true;
			//Recorremos la cadena desde la posición 1
			//y comparamos con la palabra a partir de 
			//la posición donde las dos letras iguales
			for (int j = 1; j < cadena.Length; j++)
				if (palabra[i + j] != cadena[j])
					contenida = false;
			//Si esta contenida
			if(contenida) 
				return true;
		}
	//Si no está contenida
	return false;
}

Notas

Es importante notar que aunque String, es una clase en C#, se puede tratar como un array de caracteres, y que el for se hace hasta palabra.Length-subcadena.Length, para que no de excepción. Si quieres saber más sobre este tema, puedes ver un post que escribí hace un tiempo sobre la clase String en C#. También hay que decir que este ejercicio se puede hacer de otra forma más eficiente usando String Matching y algoritmos como KMP, pero no es el objetivo de este post.

Creo que el código está bien comentado, pero cualquier pregunta en los comentarios.

Descargar Ejemplo

Puedes descargar este y otros ejemplos de string usando C#

Entradas relacionadas

Pues bien, si ya llevas algún tiempo programando, habrás notado que esto de extraer los datos de la fuente de datos y tratarlos como objetos es algo complicado, sobre todo porque existen buenas diferencias entre las bases de datos relacionales y los lenguajes orientados a objetos como C#.

Se han diseñado unas cuantas herramientas ORM (Object-Relational mapping) para resolver este problema (crear una base de datos orientada a objetos virtual), pero casi siempre dejan algo que desear, y hoy por hoy, a pesar de haber unas cuantas herramientas de uso libre y comercial, muchos programadores prefieren usar sus propias bibliotecas para trabajar con fuentes de datos.

En este contexto es que nace la idea de LINQ (Language INtegrated Query), en principio una herramienta más para dar solución al problema del mapeo objeto-relacional (ORM) y simplificar la interacción entre objetos y fuentes de datos (XML, ADO.Net, RDBMS), quién luego se convirtió en un conjunto de herramientas de consulta integrado en varios lenguajes de la plataforma .Net.

LINQ es un cambio en la forma de manejar y manipular los datos, permite el acceso a cualquier fuente de datos (LINQ to Objects, LINQ to SQL, LINQ to DataSets), mezclar datos de diferentes fuentes con una sintaxis muy sencilla, comprobar en tiempo de compilación las consultas, el uso de IntelliSense de Visual Studio y un enfoque declarativo para escribir códigos más cortos y sencillos. Funciona a partir de C# 3.0 y VB.Net 9.0 ya que requiere de ayuda por parte del compilador.

En realidad LINQ lo que provee es una capa intermedia entre la fuente de dato y el cliente, por decirlo de alguna forma. Gracias a esta abstracción es que podemos trabajar de la misma forma con LINQ sin importar que la fuente de datos sea un archivo XML o una base de datos.

Bueno,  vamos a ver algunos códigos y ejemplos de consultas LINQ y su ventaja frente a las consultas imperativas que se hacen con C# y a otras.

Nota: Para este ejemplo, vamos a suponer que tenemos ya una base de datos llamada Personal mapeada a un conjunto de clases como sigue. Noten que en muchos casos esto se puede hacer de forma automática con Visual Studio.

Esta sería la estructura de la clase que hace referencia a la base de datos:

[Table(Name="Personas")]
class Persona
{
     [Column(IsPrimaryKey=true)]
      public int ID;
 
     [Column(Name="ContactName")]
      public string Nombre;
 
     [Column(Name="ContactAge")]
      public int Edad;
 
     [Column]
      public string Ocupación;
}

Ahora vamos a obtener todas las personas que tengan menos de 30 años y que sean abogados usando LINQ:

var consulta =
            from persona in db.GetTable()
            where persona.Edad<30 && persona.Ocupacion==”abogado”
            select persona;

Y así ya dejamos de tener que hacer las consultas SQL aquellas que nos complicaban la vida, ahora todo es mucho más sencillo, y podemos mantener las mismas consultas sin importar que fuente de dato se esté usando. En el MSDN hay unos cuantos buenos ejemplos de LINQ. Terminaré con una frase que describe en dos líneas la idea esencial de LINQ:

“Before LINQ it was like you had to order your dinner in one language and drinks in another”
Jason McConnel, Product Manager for Visual Studio at Microsoft

Para seguir leyendo sobre LINQ:

Hoja de Trucos de LINQ to SQL
Ejemplo práctico con LINQ y C#
Tutorial de LINQ to SQL *

Entradas relacionadas

Se definen como métodos estáticos pertenecientes a una clase estática y no genérica; pero se llaman de la forma tradicional, como métodos de una instancia de una clase.

Se les pasa como primer parámetro this seguido del tipo de la clase a la cual se va a añadir el método; aquí tenemos un ejemplo de añadirle un método a la clase String de .Net:

public static class MyExtensions
{
     public static int WordCount(this String str)
     {
         //Split separa la cadena en un array de string utiizando los separadores especificados
         return str.Split(new char[] { ' ', '.', '?', ';' , ':' }, StringSplitOptions.RemoveEmptyEntries).Length;
     }
}

Utilizando este ejemplo:

  string s = "hello extension methods!";
  int count = s.WordCount();
  //Este código imprime: 3

Este método podrá ser usado en todas las variables de tipo string, IntelliSense también los reconoce ya que no violan los principios de encapsulación, pues en realidad no modifican a la clase ni acceden a sus variables privadas.

Los métodos extensores se usan para extender una clase o interface; pero no para sobreescribirla. Un método extensor con el mismo nombre y signatura (parámetros) que un método de la clase o la interface, nunca será llamado: en tiempo de compilación, los métodos extensores tienen menor prioridad que los métodos definidos en el propio tipo y están definidos en el ámbito del namespace.

Veamos otro ejemplo un poco más complejo usando interfaces y genericidad:

//Este método devuelve el mayor de una colección que sea 
//IEnumerable(List, array, LinkedList, etc)
public static T Mayor(this IEnumerable items) where T : IComparable
    {
      T max = default(T);
      bool empty = true;
      foreach (T x in items)
      {
        max = x; empty = false;  break;
      }
      if (empty) throw new Exception("The source cannot be empty");
      foreach (T x in items)
      {
        if (x.CompareTo(max) > 0)
          max = x;
      }
      return max;
    }

Como en el caso anterior, ahora en todas las clases que implementen la interfaz IEnumerable donde sus elementos se puedan comparar, tendremos un método Mayor, que devuelve el mayor elemento de la colección de objetos de tipo T genérico. Veamos algunos ejemplos de como usar este método:

int[] numeros = { 10, -60, 20, -50, 30, -40 };
Console.WriteLine(numeros.Mayor()=;
//se va a imprimir 30

Otro ejemplo podría ser:

List colores = new List { "rojo", "verde", "azul", "blanco", "negro"};
Console.WriteLine(colores.Mayor());
//se va a imprimir verde, que es el mayor en orden alfabético

Bueno, si quieren ver más ejemplos aquí les dejo unos cuantos métodos extensores en C# para descargar con sus probadores y todo, para que practiques y le saques el mayor partido a esta nueva característica de C#. Si tienes alguna duda, propuesta o no entiendes algo en los comentarios por favor. Proximamente estaremos hablando de LINQ, otra de las nuevas características de C# y .Net.

No hay entradas relacionadas.

Crear una aplicación de Consola:

Para esto, deberemos ir a File->New->Project si usas Visual Studio, pero con cualquier otro IDE debe ser algo parecido. Entonces se mostrará una nueva ventana como la de la figura, seleccionamos C# en el menu izquierdo y luego como tipo de proyecto marcamos “Console Apliccation”, le ponemos un nombre al proyecto y le damos Ok. Ya estaremos listos para empezar con el código.

Métodos útiles para trabajar con la consola

Para interactuar con el usuario es que existen algunos métodos básicos cuando trabajamos con la Consola. Veamos los más usados:

1- Console.WriteLine();
Escribe una nueva linea en la consola, es como presionar Enter y escribir una linea. Por ejemplo, podemos hacer:
Console.WriteLine(“Lo que quiera q salga en la consola”);
También podremos imprimir las variables de nuestro programa, para esto hay dos formas, pero veamos mejor dos ejemplos que son lo mismo:

//declaramos dos variables
string nombre = "Invitado";
int edad = 22;
//Imprimimos una linea en la consola de dos formas distintas
Console.WriteLine("Tu nombre es: "+nombre+" y tienes " + edad + " años.");
//En C# se usa el operador + para concatenar cadenas
Console.WriteLine("Tu nombre es {0} y tienes {1} años", nombre, edad);

Como ven la segunda vía es mucho más simple, solo debes recordar que el numero que está entre cochetes, es el indice del parámetro que se pasa al final del método.
2- Console.Write()
Hace casi lo mismo que Console.WriteLine() pero sin cambiar de línea, o sea… concatena el texto que le pasemos al método con lo que se haya escrito hasta ese momento en la consola.

3- Console.ReadLine()
Se usa para leer lo que el usuario escribió en la consola, y podemos guardarlo en una variable para despues usarlo en nuestro programa. No hay que pasarle ningún parámetro y el programa solo continuará cuando el usuario teclee alguna línea y presione Enter. Podemos hacer algo como esto:

Console.WriteLine("Escriba su nombre");
string nombre = Console.ReadLine();

Importante: Si lo que queremos es recoger lo que el usuario escriba como un tipo en específico, por ejemplo, un entero, deberemos usar el método estático int.Parse, por ejemplo:

int x = int.Parse(Console.ReadLine();

ya que lo que devuelve Console.ReadLine() es un string.

4-Console.ReadKey()
Este método resulta importante algunas veces, sobre todo cuando queremos darle varias opciones al usuario (a, b, c, d). Aunque se puede utilizar Console.ReadLine(). En este caso, este método lo que devuelve es un objeto de tipo ConsoleKeyInfo, y se puede utilizar de la siguiente forma, por ejemplo:

Console.WriteLine("Presiona una tecla");
ConsoleKeyInfo c = Console.ReadKey();
Console.WriteLine("Presionaste la tecla "+ c.KeyChar);

static void Main(string[] args)

public static int DameEdad(int dia, int mes, int año)
{
     //Usamos la clase DateTime y un método estatico para restar fechas
     DateTime fecha_nacimiento = new DateTime(año, mes, dia);
     TimeSpan edad = DateTime.Now.Subtract(fecha_nacimiento);
     return (edad.Days/365);
}

private static void Main(string[] args)
{
    //Variables que usaremos para la fecha de nacimiento
    int dia_nacimiento, mes_nacimiento, año_nacimiento=0;
 
    Console.WriteLine("Escriba su nombre");
    string nombre = Console.ReadLine();
    Console.WriteLine("Hola {0}, bienvenido a mi aplicacion!",nombre);
    Console.WriteLine("Por favor, introduce tu fecha de nacimiento:");
    //El while solo termina cuando se hace break
    while (true)
    {
        //Pedimos el dia y lo validamos
        Console.Write("Dia de nacimiento: ");
        dia_nacimiento = int.Parse(Console.ReadLine());
        if (dia_nacimiento < 1 || dia_nacimiento > 31)
             Console.WriteLine("Por favor, especifique un dia entre 1 y 31");
        else
             //Si el dia es valido, entonces pasamos a pedir el mes
             break;
    }
 
    while (true)
    {
        //Pedimos el mes y lo validamos
        Console.Write("Mes de nacimiento: ");
        mes_nacimiento = int.Parse(Console.ReadLine());
        if (mes_nacimiento < 1 || mes_nacimiento > 12)
             Console.WriteLine("Por favor, especifique un mes entre 1 y 12");
        else
             break;
    }
    while (true)
    {
        //Pedimos el año y lo validamos
        Console.Write("Año de nacimiento: ");
        año_nacimiento = int.Parse(Console.ReadLine());
        //El año no puede ser posterior a 1900 y anterior al año actual
        if (año_nacimiento < 1900 || año_nacimiento > DateTime.Now.Year)
             Console.WriteLine("Por favor, especifique un año entre 1900 y el {0}", DateTime.Now.Year);
        else
             break;
     }
     //Si llegamos aqui, es porque tenemos una fecha correcta, vamos a calcular la edad con
     //el método DameEdad() que escribimos antes
     int edad = DameEdad(dia_nacimiento, mes_nacimiento,año_nacimiento);
     Console.WriteLine(nombre+", usted tiene " + edad + " años.");
     Console.WriteLine("Presione cualquier tecla para terminar el programa");
     Console.ReadKey();
}

Bueno, aquí les dejo un artículo de Dan Mayer que leí hace un tiempo en Smashing Magazine, en el cual expone cinco principios para la selección y uso de tipos de letra:

“What Font Should I Use?”: Five Principles for Choosing and Using Typefaces

Otros artículos que te pueden interesar:

• How to Choose a Typeface
• Best Practices of Combining Typefaces
• The @Font-Face Rule And Useful Web Font Tricks
• The Onion Layer Model of Legibility

No hay entradas relacionadas.

Estrategia de Merge Sort

Merge Sort está basado en la técnica de diseño de algoritmos Divide y Vencerás, de la cual se habló aquí mismo hace un tiempo. Recordando un poco, esta técina consiste en dividir el problema a resolver en subproblemas del mismo tipo que a su vez se dividirán, mientras no sean suficientemente  pequeños o triviales.

Veamos una panorámica de la estrategia que sigue este algoritmo para ordenar una secuencia S de n elementos:

• Si S tiene uno o ningún elemento, está ordenada
• Si S tiene al menos dos elementos se divide en dos secuencias S1 y S2
• S1 contiene los primeros n/2 elementos y S2 los restantes
• Ordenar S1 y S2, aplicando recursivamente este procedimiento
• Mezclar S1 y S2 en S, de forma que ya S1 y S2 estén ordenados

Veamos ahora como sería la estrategia para mezclar las secuencias:

Se tienen referencias al principio de cada una de las secuencias a mezclar (S1 y S2). Mientras en alguna secuencia queden elementos, se inserta en la secuencia resultante (S) el menor de los elementos referenciados y se avanza esa referencia una posición.

Pseudocódigo

Como ven, la idea es bastante simple, pero programarla no tanto. Para no dar de golpe la solución, veamos primero un pseudocódigo del algoritmo:

function mergesort(array A[x..y])
begin
  if (x-y > 1)):
    array A1 := mergesort(A[x..(int( x+y / 2))])
    array A2 := mergesort(A[int(1+(x+y / 2))..y])
    return merge(A1, A2)
  else:
    return A
end

function merge(array A1[0..n1], array A2[0..n2])
begin
  integer p1 := 0
  integer p2 := 0
  array R[0..(n1 + n2 + 2)]//suponiendo que n1 y n2 son las posiciones
  //del array y no el length de este mismo, de otro modo seria (n1 + n2)
  while (p1 <= n1 or p2 <= n2):
    if (p1 <= n1 and A1[p1] <= A2[p2]):
      R[p1 + p2] := A1[p1]
      p1 := p1 + 1

    else
      if (p2 <= n2 and A1[p1] > A2[p2]):
        R[p1 + p2] := A2[p2]
        p2 := p2 + 1
  return R
end

El código

Básicamente, el pseudocódigo sigue la estrategia descrita anteriormente. Veamos el código en C# de una vez:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MergeSort
{
 class Program
 {
    static void Main(string[] args)
    {
       //Array desordenado inicial
       int[] nums = new int[] { 2, 7, 4, 7, 2, 9, 13, 4, 6, 8 };
       MergeSort(nums);

       //Imprimo el array ya ordenado
       for (int i = 0; i < nums.Length; i++)
          Console.Write(nums[i]+" ");
       Console.ReadLine();
    }

    //Método portal que llama al método recursivo inicial
    public static void MergeSort(int[] x)
    {
       MergeSort(x, 0, x.Length - 1);
    }

    static private void MergeSort(int[] x, int desde, int hasta)
    {
       //Condicion de parada
       if (desde == hasta)
          return;

       //Calculo la mitad del array
       int mitad = (desde + hasta) / 2;

       //Voy a ordenar recursivamente la primera mitad
       //y luego la segunda
       MergeSort(x, desde, mitad);
       MergeSort(x, mitad + 1, hasta);

       //Mezclo las dos mitades ordenadas
       int[] aux = Merge(x, desde, mitad, mitad + 1, hasta);
       Array.Copy(aux, 0, x, desde, aux.Length);
    }

    //Método que mezcla las dos mitades ordenadas
    static private int[] Merge(int[] x, int desde1, int hasta1, int desde2, int hasta2)
    {
       int a = desde1;
       int b = desde2;
       int[] result = new int[hasta1 - desde1 + hasta2 - desde2 + 2];

       for (int i = 0; i < result.Length; i++)
       {
          if (b != x.Length)
          {
             if (a > hasta1 && b <= hasta2)
             {
                result[i] = x[b];
                b++;
             }
             if (b > hasta2 && a <= hasta1)
             {
                result[i] = x[a];
                a++;
             }
             if (a <= hasta1 && b <= hasta2)
             {
                if (x[b] <= x[a])
                {
                   result[i] = x[b];
                   b++;
                }
                else
                {
                   result[i] = x[a];
                   a++;
                }
             }
          }
          else
          {
             if (a <= hasta1)
             {
                result[i] = x[a];
                a++;
             }
          }
       }
       return result;
    }
  }
}

Este código lo hice cuando estaba en 1er año, y ahora que lo veo (que ya estoy en 3ro), veo se que se pueden hacer unas cuantas mejoras, pero funciona perfectamente y está bastante comprensible, sobre todo para quien no está familiarizado con el algoritmo y la recursividad.

De todas formas dejo el zip para que puedan descargar el proyecto completo, lo único es que está en Visual Studio 2010. Si tienen alguna duda o aporte, en los comentarios.

Entradas relacionadas

Hoy les presento Graphite, un tema desarrollado por MediaLoot, con una gran calidad, muy bien diseñado y estructurado, de hecho cuenta con toda la calidad para ser de pago.

Vista previa | Download | Sitio del autor

El tema Graphite es completamente funcional, gratis y perfecto para profesionales del desarr0llo y diseño web, se adapata especialmente para sitios de empresas o portafolios.

Principales características:

• Desarrollado desde 0 usando HTML5 y CSS3
• Tipo de contenido para Portfolio
• Administracion del tema personalizado
• 2 alternativas para jquery slider en el home
• Administracion de las imágenes mostradas en el slider

En caso de que quieras buscar más temas para wordpress, o este no sea el más conveniente para tu proyecto, puedes hechar un vistazo en Smashing Magazine

Entradas relacionadas

Cual es el problema?

Una rejilla n × n es un grafo no dirigido que consiste de n filas y n columnas de vértices. El vértice de la fila i y la columna j se denota (i, j). Todos los vértices en la rejilla tienen exactamente 4 vecinos, excepto los vértices frontera que corresponden a los (i, j) para los cuales: i = 1, i = n, j = 1 o j = n. Dados m <n2 puntos iniciales (x1, y1), (x2, y2), . . . , (xm, ym) en la rejilla, el problema de la evacuación consiste en determinar si existen m caminos disjuntos (no tienen vértices comunes), que comiencen en los puntos iniciales y lleguen hasta m puntos diferentes de la frontera.

Resumen

El problema consiste en encontrar m caminos disjuntos entre dos conjuntos A y B, donde A son los m puntos de entrada y B es el conjunto de los vértices en la frontera. Primeramente se verá cómo podemos reducir el problema de encontrar m caminos vértice-disjuntos en encontrar m caminos arista-disjuntos entre dos nuevos vértices s y t transformando la entrada. En la segunda parte reduciremos el problema de saber si existen m caminos arista-disjuntos entre s y t, en un problema de flujo máximo con capacidades 1 y 0, exponiendo una condición necesaria y suficiente. Por último mostraremos un algoritmo para encontrar el flujo máximo en un grafo en O(n3).

1. Transformando la entrada

Primeramente veremos cómo el problema de encontrar m caminos vértice-disjuntos entre dos conjuntos de vértices se puede reducir a encontrar m caminos vértice-disjuntos entre dos nuevos vértices s y t.

Sean:
i. A⊂V(G) y B⊂V(G) | A∩B=∅ ^ |A|=m
ii. s y t dos nuevos vértices donde s,t ∉V(G).
iii. ∀v∈A, E(G) = E(G) + <s,v>

Sea k la cantidad de caminos vértice-disjuntos que van desde A hasta B y sea k’ la cantidad de caminos disjuntos que van de s a t, donde estos son los únicos vértices comunes en los k’ caminos, entonces k=k’, ya que aumentamos cada uno de los A-B caminos vértice-disjuntos con dos aristas <s,v0> y <vn,t> donde v0 es el primer vértice de un A-B camino y vn el último.Luego, si hacemos estos cambios al grafo de la entrada tendremos un nuevo grafo G’=<V’,E’>, donde:

V’=V+{s,t}
E’=E+{s,u}+{v,t} | u∈A ^ v∈B

Ahora convertiremos el grafo G’ en un grafo dirigido de la siguiente forma:

Por cada arista no dirigida en G’, pondremos dos aristas dirigidas, una en cada sentido. Luego, los k caminos vértice-disjuntos en G’ se mantienen luego de hacer esta transformación. Lo siguiente que haremos será convertir los caminos vértice-disjuntos en G en caminos arista-disjuntos en G´, para esto hacemos:

V’ = {vin, vout | v∈V(G)}
E’ = {(vout, win) | (v,w) ∈E(G)} ∪ {(vin, vin) | v∈V(G)}

Con las transformaciones propuestas obtenemos un nuevo grafo G’ donde cada camino vértice-disjunto en G corresponde con un camino arista-disjunto en G’ entre los vértices s y t, ya que cada camino que pasa por un vértice v pasará solo a través de la arista (vin, vout). El costo de obtener G’ a partir de G es claramente O(V), lo que en términos de la entrada sería O(n2).

2. Reduciendo el problema de encontrar k caminos arista-disjuntos a un problema de flujo máximo en una red de flujo.

En esta segunda parte, definiremos una red de flujo matemáticamente y veremos en detalle cómo resolver nuestro problema original utilizando un algoritmo para encontrar el flujo máximo en una red con capacidades de valor 1.

Sin pérdida de generalidad, sea G=<V,E> un grafo conexo y dirigido con dos vértices distinguidos s y t que llamaremos origen y destino respectivamente, donde indeg(s)=exdeg(t)=0. Definamos una función c: E→Z+ en G que llamaremos capacidad, y representa intuitivamente la cantidad máxima de flujo que puede pasar por la arista (u,v).

Diremos que un flujo s-t es una función f:E→Z+ donde el valor f(u,v) representa la cantidad de flujo que puede pasar entre los vértices u y v. El flujo f debe satisfacer las siguientes dos propiedades:

i. 0≤f(u,v)≤c(u,v), ∀(u,v)∈E(G).

ii. La sumatoria de los flujos que entran en un vértice es igual a la sumatoria de los flujos que salen de él (no lo puedo porner matemáticamente)

Obviamente la propiedad (ii) no se cumple para s y t, ya que indeg(s)=exdeg(t)=0. Llamaremos flujo de G y lo denotaremos por f(G) a la cantidad de flujo generado por s, luego f(G) es la suma de los flujos de las aristas que salen de s. El problema del flujo máximo es hallar cual es el máximo valor de f(G). O sea, ¿Cuál es la mayor cantidad de flujo que se puede enviar desde s sin violar las capacidades de las aristas? Denotaremos el flujo máximo de G como f*(G).

Volviendo a nuestro problema, después de hacer los cambios propuestos en (1) a la rejilla de entrada, tendremos un grafo D=<V,E> conexo, dirigido y dos vértices distinguidos s y t, indeg(s)=exdeg(t)=0. Luego, podemos definir un flujo s-t en D, donde en un principio todas las aristas tendrán capacidad 1 y se puede ver fácilmente que no se viola ninguna de las dos propiedades. Veamos una condición necesaria y suficiente para saber cuál es el número máximo de caminos arista disjuntos entre s y t:

Teor: El número máximo de caminos arista-disjuntos entre s y t en D, es igual al flujo máximo en D entre s y t donde todas las aristas tienen capacidad 1.

D/ Sea k el número de caminos arista-disjuntos en D entre s y t, entonces el flujo máximo f(D)≥k.

Sea P el conjunto de los k caminos disjuntos de s a t. Vamos a hacer lo siguiente:

1. f(u,v)=1 ∀(u,v)∈E(P)

2. f(u,v)=0 ∀(u,v)∉E(P)

f(u,v) solo toma valores 0 ó 1, por lo que se cumple la propiedad (i). Además, todo camino empieza en s y termina en t, y esto implica que todos los vértices interiores que participan en alguno de los k caminos arista-disjuntos tiene una arista que entra y una que sale de v con flujo 1 por construcción, por lo que se cumplirá la propiedad (ii). Luego, tendremos un flujo válido en D, f(G) =k, que son la cantidad de aristas con flujo que salen de s. Luego, f*(G) ≥f(G) ≥k.

Sea D una red de flujo, donde f(D)= k y todas las aristas tienen capacidad 1, entonces existen al menos k caminos arista-disjuntos entre s y t.

En otras palabras, lo que tenemos que demostrar es que el conjunto de aristas con f(u,v)=1 contiene un subconjunto de k caminos arista-disjuntos entre s y t, esto es porque el flujo en este caso toma siempre valores 0 ó 1, por la forma en la que construimos nuestro grafo D.

Sea f(D)=k y m’ el conjunto de aristas tal que f(u,v)=1.

Para esta demostración haremos inducción en el número de aristas con f(u,v)=1.

No hay entradas relacionadas.