Combinatoria

Combi(2)
Agustı́n Gilbert, Benjamı́n Mateluna

May 2023
1 Introducción
En las clases de combinatoria trabajamos con grafos simples, pero mientras la cantidad de grafos sea finita, entonces
podemos generalizar el concepto de grafo:
Definición 1. Un multigrafo, o grafo no simple, es un par ordenado (V, E) en donde E es un conjunto finito, y
todo elemento de E es un par no ordenado {x, y} ⇢ V .
Es decir, en un multigrafo permitimos loops (aristas que unen un vértice consigo mismo, es decir, un ciclo de
un vértice) y que entre dos vértices hayan múltiples aristas que los unen entre sı́ (ciclos de dos vértices).
Definición 2. Sea G = (V, E) un grafo, x 2 V , deg(x) := |{e 2 E : x es solo ún extremo de e}| + 2|{e 2 E :
x es ambos extremos de e}|.
En vez de contar los vecinos de un vértice para conocer su grado, contamos las aristas que salen del vértice para
conocer su grado, por suerte, no muchas cosas se alteran:
Lema 1. Para cualquier grafo G = (V, E) (simple o multigrafo), se tiene que:
X
deg(x) = 2|E|
x2V
Proof. La demostración es similar que en el caso de grafos simples, al contar aristas mediante los grados, contamos
cada arista dos veces (una vez por cada extremo de esta), por lo que al final contamos cada arista dos veces, y por
ende, se obtiene la igualdad.
Los multigrafos nos permiten trabajar con herramientas que normalmente en grafos simples deberı́amos tener
cuidado al usar:
Definición 3. Sea G = (V, E) un grafo, donde x, y son vértices distintos entre sı́ y están unidos por una única
arista, y z 2 / V, z 2/ E, la operación Contracción de la arista {x, y} es transformar el grafo G en un grafo
H = (V 0 , E 0 ) en donde
V 0 = V \ {x, y} [ z
E 0 = E \ {e 2 E : x o y es un extremo} [ {{v, z} : 9e 2 E : e = {v, x}_{v, y}, v 2 V }
(_ denota el operador lógico “o exclusivo”) Es decir, se juntan los vértices x, y, formando el vértice z, la arista
{x, y} es la única que se elimina del grafo, y aquellas aristas que iban a x o y irán ahora a z. Visualmente hablando
esto es:
1
Ahora si hay múltiples aristas {x, y} (digamos {x, y}n para las n distintas aristas {x, y}), la contracción de la arista
{x, y}1 viene dada por el mismo procedimiento, solo que las aristas {x, y}2 , ..., {x, y}n pasan a ser loops de z.
Y si queremos contraer un loop, el procedimiento cambia un poco, pues solo se elimina ese loop, es decir:
V0 =V
E 0 = E \ {loop}
Proposición 1. Sea G un grafo planar conexo, con v la cantidad de vértices, e la de aristas y f la de caras,
entonces se tiene que toda representación plana de G cumple:
v e+f =2
Proof. Se hará mediante inducción en f .

Caso base: Si f = 1, entonces tenemos un árbol (Si hubiera un ciclo, entonces por teorema de la curva de Jordan
deberı́an haber dos caras, como tenemos un componente conexo sin ciclos, tenemos un árbol). Entonces queremos
probar para el caso base que v = e + 1, lo cual se hará por inducción fuerte en v.
Caso base: Si v = 1, tenemos el grafo trivial y por ende e = 0, lo cual satisface el teorema.
Hipótesis inductiva: 9k 2 N : 8j  k, v = j ) v = e + 1.
Inducción: Sea v = k + 1, como es un árbol, existe una hoja. Si borramos la hoja junto con el vértice que
tenemos, obtenemos que v 0 = v 1 y e0 = e 1, y este nuevo árbol cumple con la fórmula de Euler, por lo que
v 1 = e 1 + 1 ) v = e + 1.
Hipótesis inductiva: 9k 2 N : (8G grafo, f = k ) v e + f = 2).
Inducción: Sea G un grafo cualquiera tal que f = k + 1, como k es natural significa que G tiene al menos un
ciclo. Borrar cualquier arista del ciclo reduce la cantidad de caras en uno y la cantidad de vértices en uno, i.e.
e0 = e 1, f 0 = f 1 = k, este nuevo grafo cumple con la fórmula de Euler, por lo que v (e 1) + (f 1) = 2 )
v e + 1 + f 1 = 2 ) v e + f = 2.
Nota: En particular, un loop es un 1-ciclo, y tener las aristas {x, y}, {x, y} forman un 2-ciclo. Por lo que por
teorema de curva de Jordan, estos tipos de ciclos también forman una cara, y por ende, el procedimiento es el
mismo.
2
Ejemplo acerca de grafos aleatorios
José Facuse, Juan Fleux, Joaquı́n Gutiérrez, Ignacio Vargas
June 2023
Téngase el siguiente teorema utilizando grafos aleatorios: 8k 3 9G = (V, E) con |V | = n y |E| = a tal que
1
Ck ⇢
6 G y a n1+ k
Nótese que este teorema nos asegura la existencia de un grafo G que cumple esas condiciones, pero no una manera
de encontrarlo (o al menos no a priori). Podrı́amos intentar buscar un método para dar con este grafo G para algún
k. Ası́, podrı́amos comenzar analizando casos pequeños.
Ejemplo 1: Encuéntrese un n lo suficientemente grande tal que 9G(V, E) con |V | = n y |E| = a tal que C k 6⇢ G y
1
a n1+ k
Solución: Ya que estamos trabajando con el k mas pequeño posible, veamos los primeros casos a mano, pues
1
estos podrı́an (o no) ser pocos. Para esto, se buscara cumplir la condición a n1+ k . Empezamos buscando con 3
vértices, luego 3 y ası́, mientras colocamos aristas hasta cumplir con la primera condición. Ası́, tenemos la siguiente
tabla:
Grafo Aristas Condición
1
3 en el mejor de los casos No cumple 3 31+ 3
1
6 en el mejor de los casos No cumple 6 41+ 3
1
9 en el mejor de los casos Si cumple 9 51+ 3 ⇡ 8.4
Luego notamos que para que nuestra condición se cumpla necesitamos examinar los grafos sin ciclos de 3 con
al menos 5 vértices. Como ya tenemos la visualización del grafo con n=5 y notamos un ciclo de 3 lo descartamos
inmediatamente.
Después de seguir con este procedimiento hasta el caso n=8 notamos nuestro primer grafo G, es cual resulta
ser K (4,4) :
1
1
Notamos que cumple la condición de aristas, pues tenemos 16 81+ 3 , en particular es igual, y además como es
bipartito sabemos que no tiene ningún ciclo de largo impar, por tanto no de largo 3.
Notamos que podemos realizar un razonamiento similar para otros k impares, pues si buscamos un grafo bipartito,
una de las condiciones se obvia. Sin embargo, no es necesario buscar mas grafos, pues sorprendentemente K (4,4)
cumple las condiciones presentadas para todo k impar.
Ejemplo 2: 8k 3 y k = 2z 1 con z 2 N tenemos que un grafo G que cumple las condiciones explicitadas
en ejemplo 1, es K (4,4)
Demostración: Como K (4,4) es bipartito sabemos que no existe ningún ciclo de largo impar en G, por tanto
ninguno de largo k. Ası́, solo debemos de fijarnos de que se cumpla la desigualdad de aristas respecto a sus vértices.
Tenemos n = 4 y a = 16 para K (4,4) y notamos que:

1 p p 1
n1+ k = n · k
n n = n1+ k+2
n· k+1
p p
Esto pues sabemos que n > 1 y k positivo mayor a uno, por lo que k+2 n  k n. Luego:
1 1 1
a = 16 41+ 3 > 41+ 5 > 41+ 7 ...
1
!a 41+ k 8 k impar
Probando la segunda condición y ası́ probando que K (4,4) cumple ambas condiciones para todo k. Finalizado el
ejercicio.

Combinatoria

Cargado por

Copyright:

Formatos disponibles

Combinatoria

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Combinatoria

Cargado por

Copyright:

Formatos disponibles

Combi(2)

Agustı́n Gilbert, Benjamı́n Mateluna

Proof. Se hará mediante inducción en f .

Grafo Aristas Condición

Tenemos n = 4 y a = 16 para K (4,4) y notamos que:

También podría gustarte