Insieme indipendente massimale e Katarzyna Dydek: differenze tra le pagine

Versione delle 21:28, 6 apr 2014

Versione delle 12:10, 9 giu 2016

Riga 1:

{{S|allenatori di pallacanestro polacchi|cestisti polacchi}}

{{T|inglese|matematica|aprile 2014}}

{{Sportivo

|Nome = Katarzyna Dydek

|NomeCompleto = Katarzyna Elżbieta Dydek

|Sesso = F

|CodiceNazione = {{POL}}

|Altezza = 197

|Peso = 86

|Disciplina = Pallacanestro

|Ruolo = [[Allenatrice]] (ex [[Centro (pallacanestro)|centro]])

|Squadra =

|TermineCarriera =

|Squadre =

{{Carriera sportivo

||{{Basket Lotos Gdynia|G}}|

|1996-1997|{{Basket Colorado Xplosion|G}}|24

}}

|SquadreNazionali=

{{Carriera sportivo

|1991-2001 |{{Naz|PC|POL|F}} |

}}

|Allenatore =

{{Carriera sportivo

||{{Basket Lotos Gdynia}}|<small>(vice)</small>

||AZS Poznan|

}}

|Vittorie =

{{MedaglieCompetizione|Europei}}

{{MedaglieOro|[[FIBA EuroBasket Women 1999|Polonia 1999]]}}

|Aggiornato =

}}

{{Bio

|Nome = Katarzyna Elżbieta

|Cognome = Dydek

|Sesso = F

|LuogoNascita = Varsavia

|GiornoMeseNascita = 21 marzo

|AnnoNascita = 1970

|LuogoMorte =

|GiornoMeseMorte =

|AnnoMorte =

|Attività = ex cestista

|Attività2 = allenatrice di pallacanestro

|Nazionalità = polacca

}}

È la sorella di [[Margo Dydek]].

==Collegamenti esterni==

{{Nota disambigua|altri significati|[[Insieme indipendente (disambigua)]]}}

*{{SchedaSR}}

{{Nota disambigua2|Questa voce tratta gli aspetti combinatori degli insiemi indipendenti massimali di vertici in un grafo. Per altri aspetti degli insiemi indipendenti di vertici nella teoria dei grafi, vedi [[Insieme indipendente (teoria dei grafi)]]}}

*{{cita web|http://archive.fiba.com/pages/eng/fa/player/p/pid/4964/sid/2268/tid/347/tid2//_/2001_European_Championship_for_Women/index.html|Scheda agli europei 2001 su fiba.com|lingua=en}}

{{Polonia femminile di pallacanestro agli europei 1991}}

[[File:Cube-maximal-independence.svg|thumb|300px|Il [[Grafo ipercubo|grafo del cubo]] ha sei diversi insiemi indipendenti massimali, mostrati come i vertici rossi.]]

{{Polonia femminile di pallacanestro agli europei 1999}}

{{Polonia femminile di pallacanestro alle olimpiadi 2000}}

Nella [[teoria dei grafi]], un '''insieme indipendente massimale''' o '''insieme stabile massimale''' è un [[Insieme indipendente (teoria dei grafi)|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;<ref>{{cita|Erdős1966||Erdős (1966)|harv=s}} 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''.</ref> un insieme indipendente massimale più grande è chiamato [[insieme indipendente massimo]].

{{Polonia femminile di pallacanestro agli europei 2001}}

{{Portale|biografie|pallacanestro}}

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 [[Spazio vettoriale|spazi vettoriali]] e nei [[Matroide|matroidi]].

== Insiemi di vertici correlati ==

Se ''S'' è un insieme indipendente massimale in qulache grafo, è una '''cricca massimale''' o un '''sottografo completo massimale''' nel [[Grafo complemento|grafo complementare]]. Una cricca massimale è un insieme di vertici che [[Sottografo indotto|induce]] un [[Grafo completo|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|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 (teoria degli insiemi)|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 [[Sfere rigide|gas di reticolo a sfere rigide]], un'astrazione matematica delle transizioni di stato fluido-solido.<ref>{{cita|Weigt2001||Weigt & Hartmann (2001)|harv=s}}.</ref>

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.

<!--

== Graph family characterizations ==

Certain graph families have also been characterized in terms of their maximal cliques or maximal independent sets. Examples include the maximal-clique irreducible and hereditary maximal-clique irreducible graphs. A graph is said to be ''maximal-clique irreducible'' if every maximal clique has an edge that belongs to no other maximal clique, and ''hereditary maximal-clique irreducible'' if the same property is true for every induced subgraph.<ref>Information System on Graph Class Inclusions: [http://wwwteo.informatik.uni-rostock.de/isgci/classes/gc_749.html maximal clique irreducible graphs] and [http://wwwteo.informatik.uni-rostock.de/isgci/classes/gc_750.html hereditary maximal clique irreducible graphs].</ref> Hereditary maximal-clique irreducible graphs include [[triangle-free graph]]s, [[bipartite graph]]s, and [[interval graph]]s.

[[Cograph]]s can be characterized as graphs in which every maximal clique intersects every maximal independent set, and in which the same property is true in all induced subgraphs.

== Bounding the number of sets ==

{{Harvtxt|Moon|Moser|1965}} showed that any graph with ''n'' vertices has at most 3^''n''/3 maximal cliques. Complementarily, any graph with ''n'' vertices also has at most 3^''n''/3 maximal independent sets. A graph with exactly 3^''n''/3 maximal independent sets is easy to construct: simply take the disjoint union of ''n''/3 [[cycle graph|triangle graphs]]. Any maximal independent set in this graph is formed by choosing one vertex from each triangle. The complementary graph, with exactly 3^''n''/3 maximal cliques, is a special type of [[Turán graph]]; because of their connection with Moon and Moser's bound, these graphs are also sometimes called Moon-Moser graphs. Tighter bounds are possible if one limits the size of the maximal independent sets: the number of maximal independent sets of size ''k'' in any ''n''-vertex graph is at most

:<math>\lfloor n/k \rfloor^{k-(n\bmod k)}\lfloor n/k+1 \rfloor^{n\bmod k}.</math>

The graphs achieving this bound are again Turán graphs.<ref>{{Harvtxt|Byskov|2003}}. For related earlier results see {{Harvtxt|Croitoru|1979}} and {{Harvtxt|Eppstein|2003}}.</ref>

Certain families of graphs may, however, have much more restrictive bounds on the numbers of maximal independent sets or maximal cliques. If all ''n''-vertex graphs in a family of graphs have O(''n'') edges, and if every subgraph of a graph in the family also belongs to the family, then each graph in the family can have at most O(''n'') maximal cliques, all of which have size O(1).<ref>{{Harvtxt|Chiba|Nishizeki|1985}}. Chiba and Nishizeki express the condition of having O(''n'') edges equivalently, in terms of the [[arboricity]] of the graphs in the family being constant.</ref> For instance, these conditions are true for the [[planar graph]]s: every ''n''-vertex planar graph has at most 3''n''&nbsp;&minus;&nbsp;6 edges, and a subgraph of a planar graph is always planar, from which it follows that each planar graph has O(''n'') maximal cliques (of size at most four). [[Interval graph]]s and [[chordal graph]]s also have at most ''n'' maximal cliques, even though they are not always [[sparse graph]]s.

The number of maximal independent sets in ''n''-vertex [[cycle graph]]s is given by the [[Perrin number]]s, and the number of maximal independent sets in ''n''-vertex [[path (graph theory)|path graphs]] is given by the [[Padovan sequence]].<ref>{{Harvtxt|Bisdorff|Marichal|2007}}; {{Harvtxt|Euler|2005}}; {{Harvtxt|Füredi|1987}}.</ref> Therefore, both numbers are proportional to powers of 1.324718, the [[plastic number]].

== Set listing algorithms ==

{{Further|Clique problem#Listing all maximal cliques}}

An algorithm for listing all maximal independent sets or maximal cliques in a graph can be used as a subroutine for solving many NP-complete graph problems. Most obviously, the solutions to the maximum independent set problem, the maximum clique problem, and the minimum independent dominating problem must all be maximal independent sets or maximal cliques, and can be found by an algorithm that lists all maximal independent sets or maximal cliques and retains the ones with the largest or smallest size. Similarly, the [[Vertex cover problem|minimum vertex cover]] can be found as the complement of one of the maximal independent sets. {{Harvtxt|Lawler|1976}} observed that listing maximal independent sets can also be used to find 3-colorings of graphs: a graph can be 3-colored if and only if the [[complement (graph theory)|complement]] of one of its maximal independent sets is [[bipartite graph|bipartite]]. He used this approach not only for 3-coloring but as part of a more general graph coloring algorithm, and similar approaches to graph coloring have been refined by other authors since.<ref>{{Harvtxt|Eppstein|2003}}; {{Harvtxt|Byskov|2003}}.</ref> Other more complex problems can also be modeled as finding a clique or independent set of a specific type. This motivates the algorithmic problem of listing all maximal independent sets (or equivalently, all maximal cliques) efficiently.

It is straightforward to turn a proof of Moon and Moser's 3^''n''/3 bound on the number of maximal independent sets into an algorithm that lists all such sets in time O(3^''n''/3).<ref>{{Harvtxt|Eppstein|2003}}. For a matching bound for the widely used [[Bron–Kerbosch algorithm]], see {{harvtxt|Tomita|Tanaka|Takahashi|2006}}.</ref> For graphs that have the largest possible number of maximal independent sets, this algorithm takes constant time per output set. However, an algorithm with this time bound can be highly inefficient for graphs with more limited numbers of independent sets. For this reason, many researchers have studied algorithms that list all maximal independent sets in polynomial time per output set.<ref>{{Harvtxt|Bomze|Budinich|Pardalos|Pelillo|1999}}; {{Harvtxt|Eppstein|2005}}; {{Harvtxt|Jennings|Motycková|1992}}; {{Harvtxt|Johnson|Yannakakis|Papadimitriou|1988}}; {{Harvtxt|Lawler|Lenstra|Rinnooy Kan|1980}}; {{Harvtxt|Liang|Dhall|Lakshmivarahan|1991}}; {{Harvtxt|Makino|Uno|2004}}; {{Harvtxt|Mishra|Pitt|1997}}; {{Harvtxt|Stix|2004}}; {{Harvtxt|Tsukiyama|Ide|Ariyoshi|Shirakawa|1977}}; {{Harvtxt|Yu|Chen|1993}}.</ref> The time per maximal independent set is proportional to that for [[matrix multiplication]] in dense graphs, or faster in various classes of sparse graphs.<ref>{{Harvtxt|Makino|Uno|2004}}; {{Harvtxt|Eppstein|2005}}.</ref>

-->

== Note ==

{{references|2}}

== Bibliografia ==

{{Div col|2}}

*{{cita testo

| cognome1 = Bisdorff | nome1 = R. | cognome2 = Marichal | nome2 = J.-L.

| titolo = Counting non-isomorphic maximal independent sets of the ''n''-cycle graph

| anno = 2007

| arxiv = math.CO/0701647

| cid = Bisdorff2007}}

*{{cita testo

| nome1 = I. M. | cognome1 = Bomze

| nome2 = M. | cognome2 = Budinich

| nome3 = P. M. | cognome3 = Pardalos

| nome4 = M. | cognome4 = Pelillo

| contributo = The maximum clique problem

| titolo = Handbook of Combinatorial Optimization

| volume = 4

| pagine = 1–74

| editore = Kluwer Academic Publishers

| anno = 1999

| id = {{citeseerx|10.1.1.48.4074}}

| cid = Bomze1999}}

*{{cita testo

| cognome = Byskov | nome = J. M.

| contributo = Algorithms for ''k''-colouring and finding maximal independent sets

| anno = 2003

| titolo = Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms

| pagine = 456–457

| url = http://portal.acm.org/citation.cfm?id=644182

| cid = Byskov2003}}

*{{cita testo

| cognome1 = Chiba | nome1 = N. | cognome2 = Nishizeki | nome2 = T.

| titolo = Arboricity and subgraph listing algorithms

| rivista = SIAM J. on Computing

| volume = 14

| numero = 1

| anno = 1985

| pagine = 210–223

| doi = 10.1137/0214017

| cid = Chiba1985}}

*{{cita testo

| cognome = Croitoru | nome = C.

| contributo = On stables in graphs

| titolo = Proc. Third Coll. Operations Research

| editore = [[Babeş-Bolyai University]], Cluj-Napoca, Romania

| anno = 1979

| pagine = 55–60

| cid = Croitoru1979}}

*{{cita testo

| cognome = Eppstein | nome = D.

| wkautore = David Eppstein

| titolo = Small maximal independent sets and faster exact graph coloring

| giornale = [[Journal of Graph Algorithms and Applications]]

| volume = 7

| numero = 2

| anno = 2003

| pagine = 131–140

| url = http://www.cs.brown.edu/publications/jgaa/accepted/2003/Eppstein2003.7.2.pdf

| arxiv = cs.DS/0011009

| cid = Eppstein2003}}

*{{cita testo

| cognome = Eppstein | nome = D.

| wkautore = David Eppstein

| contributo = All maximal independent sets and dynamic dominance for sparse graphs

| titolo = Proc. Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms

| anno = 2005

| pagine = 451–459

| arxiv = cs.DS/0407036

| cid = Eppstein2005}}

*{{cita testo

| cognome = Erdős | nome = P.

| wkautore = Paul Erdős

| titolo = On cliques in graphs

| rivista = Israel J. Math.

| volume = 4

| anno = 1966

| pagine = 233–234

| id = {{MathSciNet | id = 0205874}}

| doi = 10.1007/BF02771637

| numero = 4

| cid = Erdős1966}}

*{{cita testo

| cognome = Euler | nome = R.

| titolo = The Fibonacci number of a grid graph and a new class of integer sequences

| rivista = Journal of Integer Sequences

| volume = 8

| anno = 2005

| numero = 2

| pagine = 05.2.6

| cid = Euler2005}}

*{{cita testo

| cognome = Füredi | nome = Z. | wkautore = Zoltán Füredi

| titolo = The number of maximal independent sets in connected graphs

| rivista = Journal of Graph Theory

| volume = 11

| numero = 4

| anno = 1987

| pagine = 463–470

| doi = 10.1002/jgt.3190110403

| cid = Füredi1987}}

*{{cita testo

| cognome1 = Jennings | nome1 = E. | cognome2 = Motycková | nome2 = L.

| contributo = A distributed algorithm for finding all maximal cliques in a network graph

| titolo = Proc. First Latin American Symposium on Theoretical Informatics

| anno = 1992

| serie = Lecture Notes in Computer Science | volume = 583 | publisher = Springer-Verlag

| pagine = 281–293

| cid = Jennings1992}}

*{{cita testo

| wkautore1 = David S. Johnson| cognome1 = Johnson | nome1 = D. S.

| wkautore2 = Mihalis Yannakakis | cognome2 = Yannakakis | nome2 = M.

| wkautore3 = Christos Papadimitriou| cognome3 =Papadimitriou | nome3 = C. H.

| titolo = On generating all maximal independent sets

| rivista = Information Processing Letters

| volume = 27

| numero = 3

| pagine = 119–123

| anno = 1988

| doi = 10.1016/0020-0190(88)90065-8

| cid = Johnson1988}}

*{{cita testo

| cognome = Lawler | nome = E. L. | wkautore = Eugene Lawler

| titolo = A note on the complexity of the chromatic number problem

| rivista = Information Processing Letters

| volume = 5

| numero = 3

| pagine = 66–67

| anno = 1976

| doi = 10.1016/0020-0190(76)90065-X

| cid = Lawler1976}}

*{{cita testo

| cognome1 = Lawler | nome1 = E. L. | wkautore1 = Eugene Lawler | cognome2 = Lenstra | nome2 = J. K. | wkautore2 = Jan Karel Lenstra | cognome3 = Rinnooy Kan | nome3 = A. H. G.

| titolo = Generating all maximal independent sets: NP-hardness and polynomial time algorithms

| rivista = SIAM Journal on Computing

| volume = 9

| numero = 3

| anno = 1980

| pagine = 558–565

| doi = 10.1137/0209042

| cid = Lawler1980}}

*{{cita testo

| cognome = Leung | nome = J. Y.-T.

| titolo= Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs

| rivista = Journal of Algorithms

| volume = 5

| pagine = 22–35

| anno = 1984

| doi = 10.1016/0196-6774(84)90037-3

| cid = Leung1984}}

*{{cita testo

| cognome1 = Liang | nome1 = Y. D. | cognome2 = Dhall | nome2 = S. K. | cognome3 = Lakshmivarahan | nome3 = S.

| titolo = On the problem of finding all maximum weight independent sets in interval and circular arc graphs

| conferenza = Proc. Symp. Applied Computing

| anno = 1991

| pagine = 465–470

| cid = Liang1991}}

*{{cita testo

| cognome1 = Makino | nome1 = K. | cognome2 = Uno | nome2 = T.

| titolo = New algorithms for enumerating all maximal cliques

| conferenza = Proc. Ninth Scandinavian Workshop on Algorithm Theory

| anno = 2004

| pagine = 260–272

| url = http://www.springerlink.com/content/p9qbl6y1v5t3xc1w/

| volume = 3111

| serie = Lecture Notes in Compute Science

| editore = Springer-Verlag

| cid = Makino2004}}

*{{cita testo

| cognome1 = Mishra | nome1 = N. | cognome2 = Pitt | nome2 = L.

| contributo = Generating all maximal independent sets of bounded-degree hypergraphs

| titolo = Proc. Tenth Conf. Computational Learning Theory

| anno = 1997

| pagine = 211–217

| doi = 10.1145/267460.267500

| isbn = 0-89791-891-6

| cid = Mishra1997}}

*{{cita testo | cognome1 = Moon | nome1 = J. W. | wkautore2 = Leo Moser | cognome2 = Moser | nome2 = L. | titolo = On cliques in graphs | rivista = Israel Journal of Mathematics | volume = 3 | anno = 1965 | pagine = 23–28 | id = {{MathSciNet | id = 0182577}} | doi = 10.1007/BF02760024 | cid = Moon1965}}

*{{cita testo

| cognome = Stix | nome = V.

| titolo = Finding all maximal cliques in dynamic graphs

| rivista = Computational Optimization Appl.

| volume = 27

| numero = 2

| pages = 173–186

| anno = 2004

| doi = 10.1023/B:COAP.0000008651.28952.b6

| cid = Stix2004}}

*{{cita testo|nome1=E.|cognome1=Tomita|nome2=A.|cognome2=Tanaka|nome3=H.|cogmome3=Takahashi|titolo=The worst-case time complexity for generating all maximal cliques and computational experiments|rivista=[[Theoretical Computer Science (journal)|Theoretical Computer Science]]|volume=363|numero=1|pagine=28–42|anno=2006|doi=10.1016/j.tcs.2006.06.015|cid=Tomita2006}}

*{{cita testo

| cognome1 = Tsukiyama | nome1 = S. | cognome2 = Ide | nome2 = M. | cognome3 = Ariyoshi | nome3 = H. | cognome4 = Shirakawa | nome4 = I.

| titolo = A new algorithm for generating all the maximal independent sets

| rivista = SIAM J. on Computing

| volume = 6

| numero = 3

| pagine = 505–517

| anno = 1977

| doi = 10.1137/0206036

| cid = Tsukiyama1977}}

*{{cita testo

| cognome1 = Weigt | nome1 = Martin | cognome2 = Hartmann | nome2 = Alexander K.

| titolo = Minimal vertex covers on finite-connectivity random graphs: A hard-sphere lattice-gas picture

| anno = 2001

| rivista = Phys. Rev. E

| volume = 63

| numero = 5

| pagine = 056127

| doi = 10.1103/PhysRevE.63.056127

| arxiv = cond-mat/0011446

| cid = Weigt2001}}

*{{cita testo

| cognome1 = Yu | nome1 = C.-W. | cognome2 = Chen | nome2 = G.-H.

| titolo = Generate all maximal independent sets in permutation graphs

| rivista = Internat. J. Comput. Math.

| volume = 47

| pagine = 1–8

| anno = 1993

| doi = 10.1080/00207169308804157

| cid = Yu1993}}

{{Div col end}}

{{Portale|Matematica}}

[[Categoria:Teoria dei grafi]]

[[de:Glossar Graphentheorie#Stabile Menge]]