PRESENTACIÓN DIGRAFICAS TRANSITIVAS Y QUASITRANSITIVAS

Gráficas Transitivas y QuasiTransitivas

índice

D. transitivas

Minimal

Composición

D. Quasitransitivas

Descomposicón

Desc. total

Lema 2.7.4

Teorema 2.7.5

Repaso

Recordemos un poco por si se nos olvidó por las vacaciones

DiGráficas transitivas

Sea D una digráfica.

Para todo u, v, w en V(D), si existen las flechas uv y vw, entonces debe de existir el arco uw

Será o no será?

Minimal

Minimal en matemáticas: Sea (P, ≥) un conjunto parcialmente ordenado; m ∈ P es un elemento maximal de P si el único x ∈ P tal que m ≥ x es x = m.

Minimal en teoría de gráficas: Un (x_1,x_n)-trayectoria P, con P = x_1x_2 ...x_n es minimal si para cada (x_1,x_n)-trayectoria Q, cualquier V(P) = V (Q) o Q tiene un vértice que no vive en V (P)

Composición de Digráficas

Sea D una digráfica con los vértices {v_i : i ∈ [n]} y sean G_1, G_2, ... , G_n digráficas con conjuntos de vertices disjuntos entre si. La composición D[G_1,G_2, . . . , G_n] es la digráfica L con el conjunto de vértices V(L) = V (G_1)∪V (G_2)∪. . .∪V (G_n) y el conjunto de flechas (∪^n_{i=1}A(Gi))∪{g_ig_j : g_i ∈ V (G_i), g_j ∈ V (G_j), v_iv_j ∈ A(D)}.

Descomposición de gráficas

Una digráfica D es Φ-decomponible si D es un miembro de Φ o D = H[S_1, . . . , S_h] para algún H ∈ Φ con h = |V (H)| ≥ 2 y alguna elección de digráficas S_1, S_2, . . . , S_h

Digráficas totalmente descomponibles

Una digráfica es totalmente Φ-decomponible si cualquier D ∈ Φ o hay una Φ-decomposicion D = H[S_1, . . . , S_h] tal que h ≥ 2, y cada S_i es totalmente Φ-decomponible

Gráficas Quasi-transitivas

Sea D una digráfica.

Una digráfica es quasi-transitiva si para cada tercia x,y,z de vértices distintos en D, donde xy y yz son arcos of D, existe al menos un arco entre x y z

Entonces...

¿Son iguales las digráficas transitivas y quasi-transitivas?

Veamos si entendimos...

¿Cuál es transitiva y cuál es quasi-transitiva?

Lema

Sea D una digráfica fuerte quasi-transitiva de al menos dos vértices, entonces tenemos lo siguiente: (a) UG(D) es no conexa. (b) Si S y S' son dos subdigráficas de D tales que UG(S) y UG(S') son componentes conexas distinas de UG(D), entonces S'→S o S→S', en caso de ser ambas |V (S)| = |V (S')| = 1

tEOREMA (Pt. 1)

Sea D una digráfica quasitransitiva.

Si D no es una digráfica fuerte, entonces existe una gráfica orientada transitiva con vértices {u_1,u_2,...,u_k} y digráficas fuertes transitivas H_1,H_2,...,H_t tales que D = T[H_1,H_2,...,H_t], donde H_i es sutituido por u_i, i = {1, 2,...,t}.

tEOREMA (Pt. 2)

Sea D una digráfica quasitransitiva.

Si D es fuerte, entonces existe un digrafo fuerte semicompleto S con vertices {v_1,v_2,...,v_s} y digráficas quasi-transitivas Q_1,Q_2,...,Q_s tales que Q_i es un vértice o es no fuerte y D = S[Q_1, Q_2, ..., Q_s], donde Q_i es es sutituida por vi, i = 1, 2,...,s.

¿Dudas?

Espero que sean del tema

¡Muchas Gracias por su atención!