OII 2015/2 Reloaded

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.

OII 2015/2 Reloaded

Messaggioda cip999 » 19/09/2015, 13:03

Un grafo orientato si dice castiglionedepepolese se ha almeno due vertici e da ogni vertice esce uno e un solo arco, il quale non è un cappio. Dato un grafo castiglionedepepolese $G$, chiamiamo anticricca un sottoinsieme $S$ non vuoto dei vertici di $G$ tale che, per ogni coppia di vertici distinti $a, \: b \in S$, $a$ e $b$ non sono collegati da un arco. Definiamo sensualità di $G$ il minimo numero di anticricche in cui è possibile partizionare i vertici di $G$.
Determinare, al variare di $G$ tra tutti i grafi castiglionedepepolesi, la massima sensualità che può avere $G$, e fornire una caratterizzazione dei grafi in cui tale massimo è raggiunto.
Non so con quali armi si combatterà la Terza Guerra Mondiale, ma la Quarta sì: con bastoni e pietre.
Albert Einstein
cip999
 
Messaggi: 584
Iscritto il: 26/02/2014, 16:47

Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti