Metraipolis › archive › dc_0857abf2eb2e

Grafo di Turán — Wikipedia

Source
Wikipedia (it)
Original
https://it.wikipedia.org/wiki/Grafo_di_Tur%C3%A1n
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-07T21:55:12.742Z
SHA-256 of the archived text
d1381f4104add98fee644f139a2c7a9072d5d71acee906edeaf8a361559c1e99
Stable URL of this page
https://metraipolis.com/documento/dc_0857abf2eb2e

How to cite

Grafo di Turán — Wikipedia — Wikipedia (it), https://it.wikipedia.org/wiki/Grafo_di_Tur%C3%A1n (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_0857abf2eb2e (Metraipolis archive dc_0857abf2eb2e, sha256 d1381f4104add98fee644f139a2c7a9072d5d71acee906edeaf8a361559c1e99)
BibTeX
@misc{dc0857abf2eb2e,
  title = {Grafo di Turán — Wikipedia},
  howpublished = {Wikipedia (it)},
  url = {https://it.wikipedia.org/wiki/Grafo_di_Tur%C3%A1n},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_0857abf2eb2e; sha256 d1381f4104add98fee644f139a2c7a9072d5d71acee906edeaf8a361559c1e99},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (it), https://it.wikipedia.org/wiki/Grafo_di_Tur%C3%A1n. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Il grafo di Turán T(n,r) è un grafo formato suddividendo un insieme di n vertici in r sottoinsiemi, con dimensioni più uguali possibili, e connettendo due vertici mediante uno spigolo ogni volta che appartengono a sottoinsiemi diversi. Il grafo avrà ( n mod r ) {\displaystyle (n\,{\bmod {\,}}r)} sottoinsiemi di dimensione ⌈ n / r ⌉ {\displaystyle \lceil n/r\rceil } , e r − ( n mod r ) {\displaystyle r-(n\,{\bmod {\,}}r)} sottoinsiemi di dimensione ⌊ n / r ⌋ {\displaystyle \lfloor n/r\rfloor } . Ossia, è un grafo r-partito completo K ⌈ n / r ⌉ , ⌈ n / r ⌉ , … , ⌊ n / r ⌋ , ⌊ n / r ⌋ . {\displaystyle K_{\lceil n/r\rceil ,\lceil n/r\rceil ,\ldots ,\lfloor n/r\rfloor ,\lfloor n/r\rfloor }.} Ciascun vertice ha grado o n − ⌈ n / r ⌉ {\displaystyle n-\lceil n/r\rceil } o n − ⌊ n / r ⌋ {\displaystyle n-\lfloor n/r\rfloor } . Il numero di spigoli è 1 2 ( n 2 − ( n mod r ) ⌈ n / r ⌉ 2 − ( r − ( n mod r ) ) ⌊ n / r ⌋ 2 ) ≤ ( 1 − 1 r ) n 2 2 . {\displaystyle {\frac {1}{2}}(n^{2}-(n\,{\bmod {\,}}r)\lceil n/r\rceil ^{2}-(r-(n\,{\bmod {\,}}r))\lfloor n/r\rfloor ^{2})\leq \left(1-{\frac {1}{r}}\right){\frac {n^{2}}{2}}.} È un grafo regolare, se n è divisibile per r.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «teoria dei grafi»).
Fonte: Wikipedia in italiano, voce «Grafo di Turán» — https://it.wikipedia.org/wiki/Grafo_di_Tur%C3%A1n
Wikidata Q720459 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q720459
Autori: i contributori di Wikipedia (cronologia: https://it.wikipedia.org/wiki/Grafo_di_Tur%C3%A1n?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 148521701, consultata il 2026-10-07T21:28:54.307Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 0bc6858ef8a725fb338446c098929fa572c05d93a76c8ee495d91c9ab8e44dc1