# TDA | Practica 3 Ejercicio 3 ## Consigna $3.\star$Un $grafo\textit{ orientado ( ver Figura } {1})$ es un digrafo $D$ tal que al menos uno de $v\to w$ y $w\to v$ no es una arista de $D$,para todo $v,w\in V(D).$ En otras palabras, un grafo orientado se obtiene a partir de un grafo no orientado dando una dirección a cada arista. Demostrar en forma constructiva que para cada $n$ existe un único grafo orientado cuyos vértices tienen todos grados de salida distintos. $\textbf{Ayuda: aprovechar el ejercicio anterior y observar que el absurdo no se produce para un \' {u}nico}$ grafo orientado.  FIGURA $\mathbf{1. }( a) \textit{Un digrafo que no es grafo orientado porque tanto }1\to 4\textit{ como }4\to 1\textit{ son aristas; ( b) }$ $un\textit{ grafo orientado que se puede obtener dando orientaciones a las aristas del grafo ( c) . }$ ## Resolución - Algunas observaciones: - En un grafo orientado para cualquier par de vertices no siempre tendría aristas en ambas direcciones. - Puede haber $v\to w \ \land w\to v$ Incluso ninguna, pero no sería obligatorio que existan ambas simultaneamente para que le grafo sea orientado. - Un digrafo se puede construir a partir de un grafo no orientado, asignando una dirección a cada una de sus aristas. - a) $1 \to 4 \ \land 4 \to 1 \dots$ - b) $1 \to 2 \to 3 \to 4$ - c) acá no la veo bien # - Entonces para cada $N$ existe un unico grafo orientado, cuyos vertices tienen todos grados de salida distintos. - Hay que hacerlo por construcción. - Hay que construir un digrafo $D$ con $N$ vertices. - Sea $i$-vertice, grado de salida $d_{out}(i-1)$ para $i = \{1,2,\dots,n\}$ (toods los grados de salida distintos). - $v_1,v_2,\dots,v_n$ tal que el grado de salida de cada $v_i$ sea $i-1$ - `Para i 1...n-2:` - Añadir una arista dirigida desde el $v_i$ Hasta cada uno de los $v_{i+1},v_{i+2},v_n$ - el $v_1$ no tiene aristas salientes con grado de salida cero. - el $v_2$ tiene una arista saliente hacia $\{v_3,\dots,v_n\}$ rado de salida uno. - el $v_{\dots}$ tiene una arista saliente hacia $\{v_{...},\dots,v_n\}$ - el $v_{n-1}$ tiene $n-2$ aristas salientes $\to v_n$ con un grado de salida $n-2$. - el $v_n tiene $n-1$, grado de salida $n-1$. - Entonces sin predida de generalidad: puedo llamar $v_i$ al vértice tal que el grado de salida de $d_{out}(v_i)=i-1 \ \forall i \leq n \ \square$