Independent Set
Salve,
chiedo un piccolo aiuto.
Sto lavorando su alcuni particolari grafi, e su questi grafi devo estrapolare alcune proprietà o caratteristiche.
Una di queste è trovare il maximum independent set. Ora la questione: tale insieme, se esiste, è anche unico?
Per particolari cardinalità e tipologie degli archi ho trovato alcune definizioni che sembrano dare conferma a ciò, ma in generale non trovo una risposta unanime, voi sapete qualcosa in merito? Se no, l'insieme ha cardinalità differenti?
se mi illuminate, ringrazio
chiedo un piccolo aiuto.
Sto lavorando su alcuni particolari grafi, e su questi grafi devo estrapolare alcune proprietà o caratteristiche.
Una di queste è trovare il maximum independent set. Ora la questione: tale insieme, se esiste, è anche unico?
Per particolari cardinalità e tipologie degli archi ho trovato alcune definizioni che sembrano dare conferma a ciò, ma in generale non trovo una risposta unanime, voi sapete qualcosa in merito? Se no, l'insieme ha cardinalità differenti?
se mi illuminate, ringrazio
Risposte
Se intendi questo:
http://en.wikipedia.org/wiki/Maximal_independent_set
la questione l'ha già risolta Erdos:
http://en.wikipedia.org/wiki/Maximal_in ... ite_note-0
(boiadé nel '66, quando son nato io, badalì se è passato un'anno e via..)
Ovviamente se hai grafi orientati e/o pesati credo tu debba approfondire, ché la questione cambia un po'.
Se invece non è questo quello che intendevi, allora cosa?
http://en.wikipedia.org/wiki/Maximal_independent_set
la questione l'ha già risolta Erdos:
http://en.wikipedia.org/wiki/Maximal_in ... ite_note-0
(boiadé nel '66, quando son nato io, badalì se è passato un'anno e via..)
Ovviamente se hai grafi orientati e/o pesati credo tu debba approfondire, ché la questione cambia un po'.
Se invece non è questo quello che intendevi, allora cosa?
Ciao Rggb 
è un piacere rileggerti
allora vediamo di chiarire. Esistono due definizioni (in generale) che mi hanno fatto parecchio confondere all'inizio, non tutti gli autori utilizzano questa terminologia o si sbizzarriscono con aggettivi dei più vari o mescolando altri problemi (come cricche o matroidi) perciò "capibbi" tutto e nulla. Perciò:
1. maximal independent sets: gli insieme independenti massimali sono quelli della definizione, hanno cardinalità differenti ed hanno le limitazioni di dimensioni ad. esempio come quelle citate da te nel link dell'Erdos.
2. maximum independent set: l'insieme indipendente massimo è il più grande insieme indipendente massimale, o chiamato anche largest maximal independent set, non è unico, ma hanno tutti la stessa cardinalità.
Quello che cerco io non è nessuno dei due sopra, e da qui è nata la confusione e terminologia, ma è il smallest maximal indipendent set o che alcuni chiamano per divertirsi con le parole smallest maximum independent set. Anche qui non è unico ed ha cardinalità sempre uguale.
Citano limitazioni sul numero totale di insiemi, ma non sulla cardinalità i vari autori, perciò ti ringrazio del link, devo dire che non lo avevo visto.
Quindi dovrei essere ok per le definizioni (spero).
Ora sarà da trovare una buona approssimazione per questi problemi...
non mi preoccupo molto, li devo tutti "filtrare" i grafi, e se non hanno determinate caratteristiche essere pesati/orientati/nonorientati ecc.. conta poco (all'incirca)
PS:
'66 è una buona annata
è un piacere rileggertiallora vediamo di chiarire. Esistono due definizioni (in generale) che mi hanno fatto parecchio confondere all'inizio, non tutti gli autori utilizzano questa terminologia o si sbizzarriscono con aggettivi dei più vari o mescolando altri problemi (come cricche o matroidi) perciò "capibbi" tutto e nulla. Perciò:
1. maximal independent sets: gli insieme independenti massimali sono quelli della definizione, hanno cardinalità differenti ed hanno le limitazioni di dimensioni ad. esempio come quelle citate da te nel link dell'Erdos.
2. maximum independent set: l'insieme indipendente massimo è il più grande insieme indipendente massimale, o chiamato anche largest maximal independent set, non è unico, ma hanno tutti la stessa cardinalità.
Quello che cerco io non è nessuno dei due sopra, e da qui è nata la confusione e terminologia, ma è il smallest maximal indipendent set o che alcuni chiamano per divertirsi con le parole smallest maximum independent set. Anche qui non è unico ed ha cardinalità sempre uguale.
Citano limitazioni sul numero totale di insiemi, ma non sulla cardinalità i vari autori, perciò ti ringrazio del link, devo dire che non lo avevo visto.
Quindi dovrei essere ok per le definizioni (spero).
Ora sarà da trovare una buona approssimazione per questi problemi...
Ovviamente se hai grafi orientati e/o pesati credo tu debba approfondire, ché la questione cambia un po'.
non mi preoccupo molto, li devo tutti "filtrare" i grafi, e se non hanno determinate caratteristiche essere pesati/orientati/nonorientati ecc.. conta poco (all'incirca)
PS:
'66 è una buona annata
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo