PL5

Dimostrare che in un DAG è sempre presente un nodo senza archi entranti.

Supponiamo per assurdo che tutti i nodi abbiano almeno un arco entrante.

Prendendo i nodi man mano, l’ultimo nodo preso deve avere un arco entrante e gli unici archi entranti possibili vengono dai nodi scelti prima. Si arriva all’assurdo.

---

Contare quanti sono gli archi diretti che posso aggiungere a un DAG di $n$ nodi e $m$ archi senza aggiungere cicli.

$u_0<u_1<\dots <u_n$

posso aggiungere $u_i\to u_j$ a patto che $i<j$.

$$\frac{n(n-1)}{2}-m$$

---

$G$ è parzialmente orientato, cioè $G=(V,E_0\cup E_N)$, con $u\to v\in E_0$ (archi orientati) e $(u,v)\in E_N$ (archi non orientati)

• dimostrare che se $G_0=(V,E_0)$ è un DAG è sempre possibile orientare gli archi $E_N$ in modo che il grafo rimanga un DAG.

def orienta(n, E0, En):
	T = topologicalSort(n, E0)
	O = ordine_su_lista(T)
	forall (u, v) in En:
		if O[u] < O[v]:
			E = E \cup {u \to v}
		else:
			E = E \cup {v \to u}
 
def ordine_su_lista(T):
	O = [None for n in T]
	p = 0
	while T:
		u = T.pop()
		O[u] = p
		p = p+1
	return 0