Demos para el final Flashcards
G es bipartito <=> G no contiene ciclos de longitud impar
-> si hay un ciclo es de long par
<- definimos dos particiones que la distancia a un vertice en una sea par y en otra impar y mostramos biparticion
G grafo o multigrafo no dirigido sin vertices aislados.
G euleriano <=> G es conexo y todos sus vertices tienen grado par
-> cada vez que paso por un v entro y salgo
<- induccion, hago un ciclo y lo saco entonces me queda un grafo que por hipotesis es eulerianovich, y concateno los caminos
En un grafo conexo G , v es vértice de corte sí y sólo sí existen u y
w ∈ VG , u != v != w , tal que todo camino de u − w contiene a v .
-> si saco v se desconecta y basta tomar un v de cada componente
<- si todos los caminos pasan por v, sacando v no hay camino entre u y w, entonces es disconexo, v es de corte
G conexo
e es arista de corte <=> e no pertenece a un ciclo en G
-> por contrarreciproco, los extremos de e estan en un ciclo, asi que sacando e siguen conectados
<- por contrarreciproco, si no es de corte hay dos caminos y si hay dos caminos los uno y tengo un ciclo
G k-conexo con k >= 3 –>
G-e es (k-1)-conexo
damos un conjunto W de k-2 vertices de G-e y queremos mostrar que G-e-W es conexo
Caso 1: x,y extremos de e
hay camino x-z si saco a y, hay camino y-z si saco a x.
hay camino x-y sacando a e
Caso 2: al menos 1 no es extremo de e
u extremo de e, saco u es conexo, hay un camino
G conexo ->
kv(G) <= ke(G) <= delta
si sacamos delta aristas, lo desconecto (kv <= delta)
si un grafo es k-conexo, sacando k-1 aristas no se desconecta, luego ke >= k, (kv <= ke)
Teo de Whitney
demo en conexidad. Lo que dice el teorema es que:
G conexo con 3 o mas vertices, G es 2-conexo <=>
para todo par de vertices u, v hay por lo menos dos caminos internamente disjuntos que los unen.
sea hk(n) la minima cantidad de aristas para un grafo k-conexo con n vertices. Entonces hk(n) >= ceil( kn/2 )
usando euler y la desigualdad del delta y kv, despejando e se llega a la formula
Teorema de Euler (v- e + r = 2) en un grafo plano, conexo.
por induccion en la cantidad de aristas. hacemos un grafo con k+1 aristas (sabiendo que funciona para k) y le sacamos una arista
queda el caso conexo y el disconexo y mostramos que ambos funcionan
Suma de grado de regiones = 2e
cada arista es frontera de dos regiones por lo que cada arista aporta en 2 a la suma total de grados de las regiones
G plano, conexo, simple con al menos 3 aristas ->
e <= 3v - 6
la frontera de cada region tiene al menos 3 aristas
-> suma de regiones >= 3r -> 2e >= 3r y usando el de euler (v - e + r = 2) se llega a la expresion
Sea G un grafo plano, conexo y bipartito ->
e <= 2v - 4
la frontera de cada region tiene al menos 4 aristas
-> suma de regiones >= 4r -> 2e >= 3r y usando el de euler (v - e + r = 2) se llega a la expresion
Dos bloques diferentes de un grafo G deben tener a lo sumo un vertice en comun
supongamos dos bloques B1 y B2 tienen mas de un vertice en comun. mostramos que B1UB2 es conexo sin vertices de corte lo que contradice la maximalidad de B1 y B2
X(G+H) = X(G) + X(H)
como todos los vertices de H son adyacentes a todos los vertices de G en G + H, no se puede usar ningun color de G en H ni ninguno de H en G.
G grafo simple –> x(g) <= ∆(G ) + 1
∆(G ) = max{ g(vi ) }
pintando secuencialmente los vertices con un color no utilizado por un vecino ya pintado, obtenemos un coloreo valido con a lo sumo ∆(G ) + 1 de colores, luego la minima cantidad es eso o menos
Si G es un grafo con k vértices mutuamente adyacentes ⇒ X (G ) ≥ k
usar menos de k colores resultaria en un par de vertices de los k mutuamente adyacentes pintados del mismo color ABS! (principio del palomar)
Sea G k- crítico entonces g (vi ) ≥ k − 1 para todo vi ∈ V.
saco el vertice, pinto con k-1 colores, vuelvo a meter el vertice, hay
X(G) >= ceil( #V / α(G) )
como cada color pinta a lo sumo α vertices,
#V <= X(G) * α
pasamos dividiendo, tomamos ceiling y somos nosotros
Todo árbol con por lo menos una arista tiene por lo menos dos vértices de grado 1.
Tomamos en el arbol un camino simple maximal, los extremos son vertices de grado 1 ya que sino no seria maximal, ademas no tiene ciclos y el grafo es finito asi que se termina en algun momento y no vuelve al primer vertice.
Todo arbol con n vertices tiene n-1 aristas
Como no tiene ciclos, el grafo es plano entonces vale que v-e+r = 2
y como r = 1, nos queda que e = v-1
Sea T un grafo con n vértices (sin lazos). Entonces las siguientes
afirmaciones son equivalentes:
1 T es un árbol.
2 T no contiene ciclos y tiene n − 1 aristas.
3 T es conexo y tiene n − 1 aristas.
4 T es conexo y toda arista es una arista de corte.
5 Todo par de vértices de T están conectados por exactamente un
camino simple.
6 T no contiene ciclos y T + e tiene exactamente un ciclo.
1->2) con el teo de euler
2->3) T tiene k componentes, e = n-k -> k = 1, es conexo
3->4) si saco una arista tengo n-2 aristas osea 2 componentes
4->5) de no ser asi habria un ciclo, contradiciendo que toda e corta
5->6) la adicion de cualquier arista forma ciclo (concatenando el camino que ya existia con la arista)
6->1) mostramos que es conexo suponiendo que hay 2 componentes, si agregamos una arista entre las dos componentes esta no forma ciclo ABS!
Sea T un árbol con n vértices y sea G un grafo simple tal que
δmin(G ) ≥ n − 1 entonces T es un subgrafo de G
Por induccion en la cantidad de vertices
en la induccion, sacando una hoja, T-v es subgrafo, y como los grados son suficientes hay otro vertice en G adyacente a v, por lo que T es subgrafo
Un árbol binario completo de altura h tiene 2 ^(h+1) − 1 vértices.
Sale por induccion aplicando la hi al subarbol izquierdo y derecho
Sea T un árbol que resulta de aplicar DFS a un grafo G conexo, entonces
la raíz r de T es un vértice de corte de G sii r tiene más de un hijo en T .
-> suponemos que r tiene un solo hijo u -> el subarbol con u de raiz es recubridor de G-v -> G-v es conexo
<-hay dos hijos y por como funciona dfs, no hay aristas entre ningun ancestro/descendiente de ellos por lo que todos los caminos pasan por la raiz.
