Primer Parcial MD

Question 1

Como es el teorema de Euler

Answer 1

suma de grados = 2 x #E

Question 2

Kn

Answer 2

Grafo simple de n vertices con todas las aristas entre ellos

Question 3

Cn

Answer 3

Grafo Ciclo

Question 4

CLn

Answer 4

Escalera circular

Question 5

E de Kn

Answer 5

n(n - 1) / 2

Question 6

Qn

Answer 6

Hipercubo (n-regulares, bipartitos, Kv = n)

Question 7

Wn

Answer 7

Grafo Rueda

Question 8

Pn

Answer 8

path

Question 9

condiciones de isomorfismo

Answer 9

1) f biyectiva
2) Preserva adyacencias

Question 10

como se arma la matriz de adyaciencia

Answer 10

Aij = cantidad de aristas de i hasta j (i = j –> cantidad de lazos)

Question 11

como se arma la matriz de incidencia (no dirigido)

Answer 11

Ave = 0 si e no es extremo de v, 1 si es extremo, 2 si es lazo

Question 12

como se arma la matriz de incidencia (digrafo)

Answer 12

Ave = 0 si no es extremo, 1 si es cabeza, -1 si es cola, 2 si es lazo

Question 13

que significa que v es alcanzable desde u

Answer 13

que existe un camino u-v

Question 14

Distancia entre vertices

Answer 14

longitud del camino mas corto

Question 15

Recorrido

Answer 15

no repite e

Question 16

Camino simple

Answer 16

no repite v

Question 17

Circuito

Answer 17

recorrido cerrado (no repite e)

Question 18

Ciclo

Answer 18

camino simple cerrado (no repite v)

Question 19

xxxx Hamiltoniano (xxxx = ciclo o camino)

Answer 19

(#V >= 3) xxxx que pasa por todos los vertices del grafo

Question 20

grafo no contiene ciclos de long impar <==>

Answer 20

es bipartito

Question 21

xxxx Euleriano (xxxx = recorrido, circuito, grafo)

Answer 21

contiene todas las aristas del grafo, grafo euleriano si contiene un circuito euleriano

Question 22

Formula Dijkstra

Answer 22

L(v) = min{ L(v) ; L(u) + P(u, v) }

Question 23

Formula Floy-Warshall

Answer 23

(D^k)ij = min{ (D^k-1)ij ; (D^k-1)ik + (D^k-1)kj}

Question 24

matriz de adyacencia elevada a r, en ij es…

Answer 24

caminos de i-j de long r

Question 25

como es la desigualdad de los k que le cuesta a feli

Answer 25

k <= kv <= ke <= delta

Question 26

Como es la sintesis de Whitney

Answer 26

parto de un ciclo y voy agregando caminos simples (es 2-conexo)

Question 27

Sintesis de Tutte

Answer 27

parto de una rueda y puedo obtener el grafo con 2 operaciones:
1) agrego arista a vertices no adyacentes
2) exploto vertice de grado >= 4

(es 3-conexo)

Question 28

Como se arma un Harary (Hk,n)

Answer 28

ver en apunte los 3 casos:
k par
k impar/ n par
k impar / n impar

Question 29

si tengo una inmersion plana se cumple que: (ecuacion que de pende de v, e, r)

Answer 29

v - e + r = 2

Question 30

Euler de regiones

Answer 30

suma de grado de regiones = 2e

Question 31

desigualdad que se cumple si es (depende de e, v):
Plano
Conexo
simple

Answer 31

e <= 3v - 6

Question 32

desigualdad que se cumple si es (depende de e, v):
Plano
Conexo
simple
bipartito

Answer 32

e <= 2v - 4

Question 33

G homeomorfo con H <=>

Answer 33

se pueden obtener uno de otro con 2 operaciones:
1) subdivision por corte de aristas
2) remover debilmente un vertice

Question 34

Que dice el teorema de Kick Buttowsi (Kuratowski)

Answer 34

Un grafo es NO plano <=>

contiene un subgrafo homeomorfo al K3,3 o K5

Question 35

hk(n) = ??

hk(n) es la cantidad minima de aristas para desconectar un grafo k-conexo con n vertices

Answer 35

ceiling(kn/2)

Question 36

distancia modulo n: |i-j|sub n =

Answer 36

min{ |i-j|, n - |i-j }