Insieme indipendente massimale

Il grafo del cubo ha sei diversi insiemi indipendenti massimali, mostrati come i vertici rossi.

Nella teoria dei grafi, un insieme indipendente massimale o insieme stabile massimale è un insieme indipendente che non è un sottoinsieme di nessun altro insieme indipendente. Cioè, è un insieme S tale che ogni spigolo del grafo ha almeno un estremo non in S e ogni vertice non in S ha almeno un vicino in S. Un insieme indipendente massimale è anche un insieme dominante nel grafo, e ogni insieme dominante che è indipendente deve essere indipendente massimale, così gli insiemi massimali indipndenti sono chiamati anche insiemi dominanti indipendenti. Un grafo può avere molti insiemi indipendenti massimali di dimensioni ampiamenti variabili;^[1] un insieme indipendente massimale più grande è chiamato insieme indipendente massimo.

Per esempio, nel grafo P₃, un cammino con tre vertici a, b e c e due spigoli ab e bc, gli insiemi {b} e {a,c} sono entrambi massimalmente indipendente. L'insieme {a} è indipendente, ma non è massimalmente indipendente, perché è un sottoinsieme dell'insieme indipendente più grande {a,c}. In questo stesso grafo, le cricche massimali sono gli insiemi {a,b} e {b,c}.

La locuzione "insieme indipendente massimale" si usa anche per descrivere sottoinsiemi massimali di elementi indipendenti in strutture matematiche diverse dai grafi, e in particolare negli spazi vettoriali e nei matroidi.

Insiemi di vertici correlati

Se S è un insieme indipendente massimale in qulache grafo, è una cricca massimale o un sottografo completo massimale nel grafo complementare. Una cricca massimale è un insieme di vertici che induce un sottografo completo, e che non è un sottoinsieme dei vertici di nessun sottografo completo più grande. Cioè, è un insieme S tale che ogni coppia di vertici in S è connessa da uno spigolo e ad ogni vertice non in S manca uno spigolo per almeno un vertice in S. Un grafo può avere molte cricche massimali, di dimensioni variabili; trovare la più grande di queste è il problema della cricca massima.

Alcuni autori includono la massimalità come parte della definizione di una cricca, e si riferiscono alle cricche massimali semplicemente come cricche.

Il complemento di un insieme indipendente massimale, cioè, l'insieme di vertici non appartenenti all'insieme indipendente, forma una copertura dei vertici minimale. Cioè, il complemento è una copertura dei vertici, un insieme di vertici che include almeno un estremo di ciascuno spigolo, ed è minimale nel senso che nessuno dei suoi vertici può essere rimosso mentre si preserva la proprietà che è una copertura. Le coperture di vertici minimali sono state studiate in meccanica statistica in connessione con il modello del gas di reticolo a sfere rigide, un'astrazione matematica delle transizioni di stato fluido-solido.^[2]

Ogni insieme indipendente massimale è un insieme dominante, un insieme di vertici tale che uogni vertice nel grafo o appartiene all'insieme o è adiacente all'insieme stesso. Un insieme di vertici è un insieme indipendente massimale se e solo se è un insieme dominante indipendente.

Note

^ Erdős1966 mostra che il numero delle diverse dimensioni di insiemi indipendenti massimali in un grafo a n vertici può essere grande come n - log n - O(log log n) e non è mai più grande di n - log n.
^ Weigt2001.

Bibliografia

R. Bisdorff e J.-L. Marichal, Counting non-isomorphic maximal independent sets of the n-cycle graph, 2007, arXiv:math.CO/0701647.
I. M. Bomze, M. Budinich, P. M. Pardalos e M. Pelillo, The maximum clique problem, in Handbook of Combinatorial Optimization, vol. 4, Kluwer Academic Publishers, 1999, 1–74, CiteSeerX: 10.1.1.48.4074.
J. M. Byskov, Algorithms for k-colouring and finding maximal independent sets, in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003, 456–457.
N. Chiba e T. Nishizeki, Arboricity and subgraph listing algorithms, in SIAM J. on Computing, vol. 14, n. 1, 1985, 210–223, DOI:10.1137/0214017.
C. Croitoru, On stables in graphs, in Proc. Third Coll. Operations Research, Babeş-Bolyai University, Cluj-Napoca, Romania, 1979, 55–60.
D. Eppstein, Small maximal independent sets and faster exact graph coloring (PDF), in Journal of Graph Algorithms and Applications, vol. 7, n. 2, 2003, 131–140, arXiv:cs.DS/0011009.
D. Eppstein, All maximal independent sets and dynamic dominance for sparse graphs, in Proc. Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005, 451–459, arXiv:cs.DS/0407036.
P. Erdős, On cliques in graphs, in Israel J. Math., vol. 4, n. 4, 1966, 233–234, DOI:10.1007/BF02771637, MR 0205874.
R. Euler, The Fibonacci number of a grid graph and a new class of integer sequences, in Journal of Integer Sequences, vol. 8, n. 2, 2005, 05.2.6.
Z. Füredi, The number of maximal independent sets in connected graphs, in Journal of Graph Theory, vol. 11, n. 4, 1987, 463–470, DOI:10.1002/jgt.3190110403.
E. Jennings e L. Motycková, A distributed algorithm for finding all maximal cliques in a network graph, in Proc. First Latin American Symposium on Theoretical Informatics, Lecture Notes in Computer Science, vol. 583, 1992, 281–293.
D. S. Johnson, M. Yannakakis e C. H. Papadimitriou, On generating all maximal independent sets, in Information Processing Letters, vol. 27, n. 3, 1988, 119–123, DOI:10.1016/0020-0190(88)90065-8.
E. L. Lawler, A note on the complexity of the chromatic number problem, in Information Processing Letters, vol. 5, n. 3, 1976, 66–67, DOI:10.1016/0020-0190(76)90065-X.
E. L. Lawler, J. K. Lenstra e A. H. G. Rinnooy Kan, Generating all maximal independent sets: NP-hardness and polynomial time algorithms, in SIAM Journal on Computing, vol. 9, n. 3, 1980, 558–565, DOI:10.1137/0209042.
J. Y.-T. Leung, Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs, in Journal of Algorithms, vol. 5, 1984, 22–35, DOI:10.1016/0196-6774(84)90037-3.
Y. D. Liang, S. K. Dhall e S. Lakshmivarahan, On the problem of finding all maximum weight independent sets in interval and circular arc graphs, Proc. Symp. Applied Computing, 1991, 465–470.
K. Makino e T. Uno, New algorithms for enumerating all maximal cliques, Proc. Ninth Scandinavian Workshop on Algorithm Theory, Lecture Notes in Compute Science, vol. 3111, Springer-Verlag, 2004, 260–272.
N. Mishra e L. Pitt, Generating all maximal independent sets of bounded-degree hypergraphs, in Proc. Tenth Conf. Computational Learning Theory, 1997, 211–217, DOI:10.1145/267460.267500, ISBN 0-89791-891-6.
J. W. Moon e L. Moser, On cliques in graphs, in Israel Journal of Mathematics, vol. 3, 1965, 23–28, DOI:10.1007/BF02760024, MR 0182577.
V. Stix, Finding all maximal cliques in dynamic graphs, in Computational Optimization Appl., vol. 27, n. 2, 2004, DOI:10.1023/B:COAP.0000008651.28952.b6.
E. Tomita, A. Tanaka e H., The worst-case time complexity for generating all maximal cliques and computational experiments, in Theoretical Computer Science, vol. 363, n. 1, 2006, 28–42, DOI:10.1016/j.tcs.2006.06.015.
S. Tsukiyama, M. Ide, H. Ariyoshi e I. Shirakawa, A new algorithm for generating all the maximal independent sets, in SIAM J. on Computing, vol. 6, n. 3, 1977, 505–517, DOI:10.1137/0206036.
Martin Weigt e Alexander K. Hartmann, Minimal vertex covers on finite-connectivity random graphs: A hard-sphere lattice-gas picture, in Phys. Rev. E, vol. 63, n. 5, 2001, 056127, DOI:10.1103/PhysRevE.63.056127, arXiv:cond-mat/0011446.
C.-W. Yu e G.-H. Chen, Generate all maximal independent sets in permutation graphs, in Internat. J. Comput. Math., vol. 47, 1993, 1–8, DOI:10.1080/00207169308804157.

Portale Matematica: accedi alle voci di Wikipedia che trattano di Matematica

[1] Erdős1966 mostra che il numero delle diverse dimensioni di insiemi indipendenti massimali in un grafo a n vertici può essere grande come n - log n - O(log log n) e non è mai più grande di n - log n.

[2] Weigt2001.

[1]

[2]