Граф товаришування (або граф данського млина, або n-лопатевий вентилятор) Fn — це планарний неорієнтований граф з 2n+1 вершинами і 3n ребрами.
Граф товаришування | |
---|---|
(Вершин) | 2n+1 |
(Ребер) | 3n |
(Радіус) | 1 |
(Діаметр) | 2 |
(Обхват) | 3 |
Хроматичне число | 3 |
Хроматичний індекс | 2n |
Властивості | граф одиничних відстаней планарний ейлерів |
Граф товаришування Fn можна побудувати, з'єднавши n копій циклів C3 в одній спільній вершині.
З побудови граф товаришування Fn ізоморфний вітряку Wd(3,n). Граф є графом одиничних відстаней, має обхват 3, діаметр 2 і радіус 1. Граф F2 ізоморфний метелику.
Теорема про граф товаришування
Теорема про граф товаришування Ердеша, Реньї і Шош стверджує, що скінченні графи з властивістю, що будь-які дві вершини мають рівно одного спільного сусіда, це в точно графи товаришування. Неформально, якщо група людей має властивість, що будь-яка пара людей має рівно одного спільного друга, то має бути одна особа, яка є другом решти членів групи. Для нескінченних графів, однак, може існувати багато різних графів однакової потужності, що мають цю властивість.
Комбінаторне доведення теореми про граф товаришування дали Мертціос і Унгер. Інше доведення дав Крейг Хунеке.
Розмітка і розфарбування
Граф товаришування має хроматичне число 3 і хроматичний Індекс 2n. Його хроматичний многочлен можна отримати з хроматичного многочлена циклу C3, він дорівнює .
Граф товаришування Fn має тоді і тільки тоді, коли n непарне. Він має граціозну розмітку тоді і тільки тоді, коли n ≡ 0 (mod 4), або n ≡ 1 (mod 4).
Будь-який граф товаришування є .
Екстремальна теорія графів
Згідно з екстремальною теорією графів будь-який граф з досить великим числом ребер (відносно числа вершин) повинен містити, як підграф, k-лопатевий вітряк. Точніше, це істинне для графа з n вершинами, якщо число ребер дорівнює
де f(k) дорівнює k2 − k, якщо k непарне, і f(k) дорівнює k2 − 3k/2, якщо k парне. Ці межі узагальнюють теорему Турана про число ребер у графі без трикутників і вони є кращими межами для цієї задачі, оскільки для будь-якого меншого числа ребер існують графи, що не містять k-лопатевого вітряка.
Примітки
- Weisstein, Eric W. Dutch Windmill Graph(англ.) на сайті Wolfram MathWorld.
- Gallian, 2007, с. 1-58.
- Erdős, Rényi, Sós, 1966.
- Erdős, Rényi, Sós, 1966, с. 215–235.
- Chvátal, Kotzig, Rosenberg, Davies, 1976, с. 431–433.
- Mertzios, Unger, 2008.
- Huneke, 2002, с. 192–194.
- Bermond, Brouwer, Germa, 1978, с. 35-38.
- Bermond, Kotzig, Turgeon, 1978, с. 135-149.
- Erdős, Füredi, Gould, Gunderson, 1995, с. 89–100.
Література
- [en]. Dynamic Survey DS6: Graph Labeling // Electronic J. Combinatorics. — 2007. — Jan.. з джерела 31 січня 2012.
- J.C. Bermond, [en], A. Germa. Systèmes de triplets et différences associées // Problèmes Combinatoires et Théorie des Graphes. — Paris, 1978. — Т. 260, Editions du Centre Nationale de la Recherche Scientifique. — (Colloq. Intern. du CNRS)
- J. C. Bermond, [en], J. Turgeon. On a combinatorial problem of antennas in radioastronomy, in Combinatorics // Colloq. Math. Soc. János Bolyai, / A. Hajnal, V. T. Sos, eds. — North-Holland, Amsterdam, 1978. — Т. 18, 2 vols.
- Paul Erdős, Alfréd Rényi, Vera T. Sós. On a problem of graph theory // Studia Sci. Math. Hungar.. — 1966. — Т. 1 (4 липня). — С. 215–235. з джерела 8 серпня 2021. Процитовано 1 серпня 2021.
- Václav Chvátal, Anton Kotzig, Ivo G. Rosenberg, Roy O. Davies. There are friendship graphs of cardinal // Canadian Mathematical Bulletin. — 1976. — Т. 19, вип. 4 (4 липня). — С. 431–433. — DOI: .
- George Mertzios, Walter Unger. The friendship problem on graphs // Relations, Orders and Graphs: Interaction with Computer Science. — 2008. — 4 липня.
- Craig Huneke. The Friendship Theorem // The American Mathematical Monthly. — 2002. — Т. 109, вип. 2 (January). — С. 192–194. — DOI: .
- Paul Erdős, Z. Füredi, R. J. Gould, D. S. Gunderson. Extremal graphs for intersecting triangles // Journal of Combinatorial Theory. — 1995. — Т. 64, вип. 1 (4 липня). — С. 89–100. — (Series B). — DOI: .
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Graf tovarishuvannya abo graf danskogo mlina abo n lopatevij ventilyator Fn ce planarnij neoriyentovanij graf z 2n 1 vershinami i 3n rebrami Graf tovarishuvannyaVershin2n 1Reber3nRadius1Diametr2Obhvat3Hromatichne chislo3Hromatichnij indeks2nVlastivostigraf odinichnih vidstanej planarnij ejlerivGrafi tovarishuvannya F2 F3 i F4 Graf tovarishuvannya Fn mozhna pobuduvati z yednavshi n kopij cikliv C3 v odnij spilnij vershini Z pobudovi graf tovarishuvannya Fn izomorfnij vitryaku Wd 3 n Graf ye grafom odinichnih vidstanej maye obhvat 3 diametr 2 i radius 1 Graf F2 izomorfnij meteliku Teorema pro graf tovarishuvannyaTeorema pro graf tovarishuvannya Erdesha Renyi i Shosh stverdzhuye sho skinchenni grafi z vlastivistyu sho bud yaki dvi vershini mayut rivno odnogo spilnogo susida ce v tochno grafi tovarishuvannya Neformalno yaksho grupa lyudej maye vlastivist sho bud yaka para lyudej maye rivno odnogo spilnogo druga to maye buti odna osoba yaka ye drugom reshti chleniv grupi Dlya neskinchennih grafiv odnak mozhe isnuvati bagato riznih grafiv odnakovoyi potuzhnosti sho mayut cyu vlastivist Kombinatorne dovedennya teoremi pro graf tovarishuvannya dali Mertcios i Unger Inshe dovedennya dav Krejg Huneke Rozmitka i rozfarbuvannyaGraf tovarishuvannya maye hromatichne chislo 3 i hromatichnij Indeks 2n Jogo hromatichnij mnogochlen mozhna otrimati z hromatichnogo mnogochlena ciklu C3 vin dorivnyuye x 2 n x 1 nx displaystyle x 2 n x 1 n x Graf tovarishuvannya Fn maye todi i tilki todi koli n neparne Vin maye gracioznu rozmitku todi i tilki todi koli n 0 mod 4 abo n 1 mod 4 Bud yakij graf tovarishuvannya ye Ekstremalna teoriya grafivZgidno z ekstremalnoyu teoriyeyu grafiv bud yakij graf z dosit velikim chislom reber vidnosno chisla vershin povinen mistiti yak pidgraf k lopatevij vitryak Tochnishe ce istinne dlya grafa z n vershinami yaksho chislo reber dorivnyuye n24 f k displaystyle left lfloor frac n 2 4 right rfloor f k de f k dorivnyuye k2 k yaksho k neparne i f k dorivnyuye k2 3k 2 yaksho k parne Ci mezhi uzagalnyuyut teoremu Turana pro chislo reber u grafi bez trikutnikiv i voni ye krashimi mezhami dlya ciyeyi zadachi oskilki dlya bud yakogo menshogo chisla reber isnuyut grafi sho ne mistyat k lopatevogo vitryaka PrimitkiWeisstein Eric W Dutch Windmill Graph angl na sajti Wolfram MathWorld Gallian 2007 s 1 58 Erdos Renyi Sos 1966 Erdos Renyi Sos 1966 s 215 235 Chvatal Kotzig Rosenberg Davies 1976 s 431 433 Mertzios Unger 2008 Huneke 2002 s 192 194 Bermond Brouwer Germa 1978 s 35 38 Bermond Kotzig Turgeon 1978 s 135 149 Erdos Furedi Gould Gunderson 1995 s 89 100 Literatura en Dynamic Survey DS6 Graph Labeling Electronic J Combinatorics 2007 Jan z dzherela 31 sichnya 2012 J C Bermond en A Germa Systemes de triplets et differences associees Problemes Combinatoires et Theorie des Graphes Paris 1978 T 260 Editions du Centre Nationale de la Recherche Scientifique Colloq Intern du CNRS J C Bermond en J Turgeon On a combinatorial problem of antennas in radioastronomy in Combinatorics Colloq Math Soc Janos Bolyai A Hajnal V T Sos eds North Holland Amsterdam 1978 T 18 2 vols Paul Erdos Alfred Renyi Vera T Sos On a problem of graph theory Studia Sci Math Hungar 1966 T 1 4 lipnya S 215 235 z dzherela 8 serpnya 2021 Procitovano 1 serpnya 2021 Vaclav Chvatal Anton Kotzig Ivo G Rosenberg Roy O Davies There are 2ℵa displaystyle scriptstyle 2 aleph alpha friendship graphs of cardinal ℵa displaystyle scriptstyle aleph alpha Canadian Mathematical Bulletin 1976 T 19 vip 4 4 lipnya S 431 433 DOI 10 4153 cmb 1976 064 1 George Mertzios Walter Unger The friendship problem on graphs Relations Orders and Graphs Interaction with Computer Science 2008 4 lipnya Craig Huneke The Friendship Theorem The American Mathematical Monthly 2002 T 109 vip 2 January S 192 194 DOI 10 2307 2695332 Paul Erdos Z Furedi R J Gould D S Gunderson Extremal graphs for intersecting triangles Journal of Combinatorial Theory 1995 T 64 vip 1 4 lipnya S 89 100 Series B DOI 10 1006 jctb 1995 1026