Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Граф Генсона Gi це неорієнтований нескінченний граф єдиний зліченний однорідний граф що не містить клік з i вершинами ал

Граф Генсона

Граф Генсона

Граф Генсона Gi — це неорієнтований нескінченний граф, єдиний зліченний однорідний граф, що не містить клік з i вершинами, але містить як підграфи всі вільні від Ki графи. Наприклад, G3 є графом без трикутників, що містить усі скінченні вільні від трикутників графи.

Графи названо ім'ям К. Ворда Генсона, який опублікував їх побудову 1971 року (для всіх ). Перший із цих графів G3 називають однорідним вільним від трикутників графом або універсальним вільним від трикутників графом.

Побудова

Для побудови цих графів Генсон упорядковує вершини графа Радо в послідовність із властивістю, що для будь-якої скінченної множини S вершин існує нескінченно багато вершин, що мають S як множину найраніших сусідів (існування такої послідовності єдиним чином визначає граф Радо). Потім він визначає Gi як породжений підграф графа Радо, утворений видаленням кінцевих вершин (у вибраному порядку) будь-якої i-кліки графа Радо.

За такої побудови будь-який граф Gi є породженим підграфом графа Gi + 1, а об'єднанням цього ланцюжка підграфів є сам граф Радо. Оскільки в будь-якому графі Gi виключено щонайменше одну вершину i-кліки графа Радо, в Gi не може бути i-клік.

Універсальність

Будь-який скінченний або зліченний вільний від i-клік граф H можна знайти як породжений підграф графа Gi послідовним додаванням вершин, раніші вершини яких у Gi відповідають множині раніших сусідів відповідних вершин в H. Таким чином, Gi є універсальним графом для сімейства вільних від i-клік графів.

Оскільки існують вільні від i-клік графи з довільно великим хроматичним числом, граф Генсона має нескінченне хроматичне число. Строгіше, якщо граф Генсона Gi розбити на будь-яке скінченне число породжених підграфів, то щонайменше один з цих графів включає всі вільні від i-клік скінченні графи як породжені підграфи.

Симетрія

Подібно до графа Радо, граф G3 містить двонаправлений гамільтонів шлях, такий, що будь-яка симетрія шляху є симетрією всього графа. Однак це не так для Gi, коли i > 3 — для цих графів будь-який автоморфізм графа має більше однієї орбіти.

Примітки

  1. Henson, 1971, с. 69–83.

Література

  • C. Ward Henson. A family of countable homogeneous graphs // . — 1971. — Т. 38 (16 червня). — С. 69–83. — DOI:10.2140/pjm.1971.38.69.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Graf Gensona Gi ce neoriyentovanij neskinchennij graf yedinij zlichennij odnoridnij graf sho ne mistit klik z i vershinami ale mistit yak pidgrafi vsi vilni vid Ki grafi Napriklad G3 ye grafom bez trikutnikiv sho mistit usi skinchenni vilni vid trikutnikiv grafi Grafi nazvano im yam K Vorda Gensona yakij opublikuvav yih pobudovu 1971 roku dlya vsih i 3 displaystyle i geqslant 3 Pershij iz cih grafiv G3 nazivayut odnoridnim vilnim vid trikutnikiv grafom abo universalnim vilnim vid trikutnikiv grafom PobudovaDlya pobudovi cih grafiv Genson uporyadkovuye vershini grafa Rado v poslidovnist iz vlastivistyu sho dlya bud yakoyi skinchennoyi mnozhini S vershin isnuye neskinchenno bagato vershin sho mayut S yak mnozhinu najranishih susidiv isnuvannya takoyi poslidovnosti yedinim chinom viznachaye graf Rado Potim vin viznachaye Gi yak porodzhenij pidgraf grafa Rado utvorenij vidalennyam kincevih vershin u vibranomu poryadku bud yakoyi i kliki grafa Rado Za takoyi pobudovi bud yakij graf Gi ye porodzhenim pidgrafom grafa Gi 1 a ob yednannyam cogo lancyuzhka pidgrafiv ye sam graf Rado Oskilki v bud yakomu grafi Gi viklyucheno shonajmenshe odnu vershinu i kliki grafa Rado v Gi ne mozhe buti i klik UniversalnistBud yakij skinchennij abo zlichennij vilnij vid i klik graf H mozhna znajti yak porodzhenij pidgraf grafa Gi poslidovnim dodavannyam vershin ranishi vershini yakih u Gi vidpovidayut mnozhini ranishih susidiv vidpovidnih vershin v H Takim chinom Gi ye universalnim grafom dlya simejstva vilnih vid i klik grafiv Oskilki isnuyut vilni vid i klik grafi z dovilno velikim hromatichnim chislom graf Gensona maye neskinchenne hromatichne chislo Strogishe yaksho graf Gensona Gi rozbiti na bud yake skinchenne chislo porodzhenih pidgrafiv to shonajmenshe odin z cih grafiv vklyuchaye vsi vilni vid i klik skinchenni grafi yak porodzheni pidgrafi SimetriyaPodibno do grafa Rado graf G3 mistit dvonapravlenij gamiltoniv shlyah takij sho bud yaka simetriya shlyahu ye simetriyeyu vsogo grafa Odnak ce ne tak dlya Gi koli i gt 3 dlya cih grafiv bud yakij avtomorfizm grafa maye bilshe odniyeyi orbiti PrimitkiHenson 1971 s 69 83 LiteraturaC Ward Henson A family of countable homogeneous graphs 1971 T 38 16 chervnya S 69 83 DOI 10 2140 pjm 1971 38 69

Дата публікації:
Топ