Grafi, classi di equivalenza e grafi densi
Ho un dubbio sulel classi di equivalenza.Nella definizione che ho io una classe di equivalenza è l' insieme dei vertici di un grafo che da lo stesso resto con la divizsione per n.Non sono sicuro di questa definizione, bisogna dividere il grado dei vertici per un numero n arbitrario?
Ad esempio s eho un grafo completo con 3 vertici G=(V,L) (in pratica è un triangolo) formato dai vertici v1,v2,v3, allora questo ha una sola classe di equivalenza perchè i vertici hanno lo stesso grado, giusto?
Poi in merito alla definizione di grafo denso ho delle definizioni contrastanti. Se G=(V,L), e |V| è il numero dei vertici, |L| è il numero dei lati, allora il grafo è denso se |L| <= |V|^2
Oppure se |V| <= |L|^2 ?
E potreste farmi un esempio di grafo denso?
Ad esempio s eho un grafo completo con 3 vertici G=(V,L) (in pratica è un triangolo) formato dai vertici v1,v2,v3, allora questo ha una sola classe di equivalenza perchè i vertici hanno lo stesso grado, giusto?
Poi in merito alla definizione di grafo denso ho delle definizioni contrastanti. Se G=(V,L), e |V| è il numero dei vertici, |L| è il numero dei lati, allora il grafo è denso se |L| <= |V|^2
Oppure se |V| <= |L|^2 ?
E potreste farmi un esempio di grafo denso?
Risposte
Ciao,
per il tuo secondo quesito, cioè la definizione di grafo denso.
Un grafo denso si definisce, con la tua terminlogia, come $|V|=|L|^2$, cioè è "al massimo" completamente connesso, ogni vertice è coperto.
Un grafo sparso $|L|inO(|V|)$ è "al massimo" un albero. Pratiamente ogni vertice è connesso al più ad un solo vertice.
per il tuo secondo quesito, cioè la definizione di grafo denso.
Un grafo denso si definisce, con la tua terminlogia, come $|V|=|L|^2$, cioè è "al massimo" completamente connesso, ogni vertice è coperto.
Un grafo sparso $|L|inO(|V|)$ è "al massimo" un albero. Pratiamente ogni vertice è connesso al più ad un solo vertice.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo