precisazione
docente
--------------------------- snip snip
secondo la tua terminologia allora è d-regolare: ogni nodo ha d archi
incidenti su di esso, che possono o meno essere paralleli
2010/1/14 Alessandro Epasto <aep...@gmail.com>
Buonasera prof. Panconesi,
Le volevo chiedere dei chiarimenti circa l'interpretazione
dell'esercizio 6.3 del libro "Concentration...." oggetto di prova
d'esame.
Il testo dell'esercizio è:
"Let G be a d-uniform, bipartite multigraph; i.e. parallel edges
are allowed.
Each edge selects a tentative color in [d] independently at
random.
An edge colors successfully if and only if its tentative color is
not
chosen by any of the incident edges.... "
La domanda è se il grafo è effettivamente d-uniform e non d-
regolare,
e se gli archi paralleli siano incidenti tra loro.
La mia interpretazione dell'esercizio era che ogni nodo ha
esattamente
d archi uscenti, eventualmente paralleli o meno tra di loro.
Quindi
non è conosciuto il numero di vicini che è comunque inferiore a d.
Inoltre gli archi paralleli sono incidenti.
Confrontandomi con altri studenti ho saputo che tale
interpretazione
equivale a d-regolare, mentre, d-uniforme significa che il numero
di
archi uscenti è arbitrario, ma che ogni arco ha altri d-1
paralleli ad
esso. Questa interpretazione mi sembrava meno coerente con il
fatto
che i colori sono in numero di [d]. Qualora l'interpretazione
esatta
fosse questa, volevo chiederle se d può essere assunto costante
nell'esercizio.
La ringrazio in anticipo. Buona serata.
--
Alessandro Epasto