www.wikidata.uk-ua.nina.az

Панциклічний граф Панциклі чний граф орієнтований або неорієнтований граф який містить цикли всіх можливих довжин від тр

Панциклічний граф

Панциклі́чний граф — орієнтований або неорієнтований граф, який містить цикли всіх можливих довжин від трьох до числа вершин графа. Панциклічні графи є узагальненням гамільтонових графів, графів, які мають цикли найбільшої можливої довжини.

Цикли всіх можливих довжин у графі октаедр показують, що граф панциклічний

Визначення ред.

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

Двочастинний граф не може бути панциклічним, оскільки він не містить циклів будь-якої непарної довжини, але кажуть, що граф є біпанциклічним, якщо він містить цикли всіх парних довжин від 4 до .

Планарні графи ред.

Максимальний зовніпланарний граф — це граф, утворений із простого многокутника на площині шляхом тріангуляції його внутрішності. Будь-який максимальний зовніпланарний граф є панциклічним, що можна показати індукцією. Зовнішня грань графа є циклом з n вершинами, а видалення будь-якого трикутника, з'єднаного із рештою графа тільки одним ребром (листок дерева, яке утворює двоїстий граф тріангуляції), утворює максимальний зовніпланарний граф з на одиницю меншим числом вершин, а за індукційним припущенням цей граф має всі цикли всіх довжин, що залишилися. Якщо приділяти більше уваги вибору трикутника для видалення, то ті самі аргументи показують строгіший результат, що будь-який максимальний зовніпланарний граф є вершинно панциклічним. Те ж саме істинне для графів, які мають максимальний зовніпланарний граф як кістяковий підграф, зокрема, для колеса.

Максимальний планарний граф — це планарний граф, у якому всі грані, включно із зовнішньою, є трикутниками. Максимальний планарний граф є вершинно панциклічним тоді й лише тоді, коли він містить гамільтонів цикл — якщо він не гамільтонів, він безумовно не панциклічний, а якщо він гамільтонів, то внутрішність гамильтонового циклу утворює зовнішню межу максимального зовнішпланарного графа на тих самих вершинах і ребрах, до якої можна застосувати попередні аргументи для зовніпланарних графів. Наприклад, на малюнку вгорі показано панциклічність графа октаедра, гамільтонового максимального планарного графа з шістьма вершинами. Строгіше, з тих самих причин, якщо максимальний планарний граф має цикл довжини , то він має цикли всіх менших довжин.

Майже панциклічний граф Халіна з циклами всіх довжин аж до n, за винятком довжини 8

Графи Халіна є планарними графами, утвореними з планарного малюнка дерева, яке має вершин степеня два, доданням циклу, що з'єднує листки дерева. Графи Халіна не обов'язково панциклічні, але вони майже панциклічні в тому сенсі, що відсутній цикл максимум однієї довжини. Довжина відсутнього циклу обов'язково парна. Якщо жодна зі внутрішніх вершин графа Халіна не має степеня три, то граф обов'язково панциклічний.

1971 року помічено, що багато класичних умов для існування гамільтонового циклу достатні також для панциклічності, тому припущено, що будь-який 4-зв'язний планарний граф панциклічний, але незабаром знайдено сімейство контрприкладів.

Турніри ред.

Турнір — це напрямлений граф з однією напрямленою дугою між будь-якою парою вершин. Інтуїтивно турнір можна використати для моделювання кругової системи малюванням дуги від переможця до переможеного для кожної гри в змаганні. Турнір називають сильно зв'язним або просто сильним тоді й лише тоді, коли його не можна розділити на дві непорожні підмножини і тих, хто програв і виграв, так, що будь-який учасник перемагає будь-якого учасника в . Будь-який сильний турнір є панциклічним і вершинно панциклічним. Якщо турнір регулярний (будь-який учасник має таке ж число виграшів і програшів, що й інші учасники), то він є також реберно панциклічним, однак сильні турніри з чотирма вершинами не можуть бути реберно панциклічними.

Графи з великим числом ребер ред.

Теорема Мантеля стверджує, що будь-який неорієнтований граф із вершинами, що має принаймні ребер і не має кратних ребер і петель, або містить трикутник, або він є повним двочастинним графом . Цю теорему можна посилити — будь-який неорієнтований гамільтонів граф з не менш ніж ребрами або панциклічний, або це .

Існують гамільтонові орієнтовані графи з вершинами і з дугами, які не є панциклічними, але будь-який гамільтонів орієнтований граф принаймні з дугами панциклічний. Крім того, строго зв'язний граф з вершинами, в якому кожна вершина має степінь, не менший від (вхідні та вихідні дуги рахуються разом), або панциклічний, або є повним двочастинним графом.

Степені графа ред.

Для будь-якого графа його -й степінь графа визначається як граф на тій самій множині вершин, що має ребро між будь-якими двома вершинами, відстань між якими в не перевищує . Якщо вершинно 2-зв'язний, то за теоремою Фляйшнера є гамільтоновим графом. Твердження можна посилити: граф обов'язково буде вершинно панциклічним. Строгіше, якщо є гамільтоновим, він також і панциклічний.

Обчислювальна складність ред.

Перевірка графа на панциклічність є NP-повною задачею навіть для окремого випадку 3-зв'язних кубічних графів. NP-повною задачею є також перевірка графа на вершинну панциклічність навіть для окрмого випадку поліедральних графів. Також NP-повною задачею є перевірка квадрата графа на гамільтоновість, а тим самим і перевірка на панциклічність.

Історія ред.

Панциклічність уперше досліджували Харарі і Мозер у контексті турнірів, а також Муун і Алпач. Назву поняттю панциклічності дав Бонді, який розширив поняття для неорієнтованих графів.

Примітки ред.

  1. ↑ Bondy, 1971.
  2. ↑ Randerath, Schiermeyer, Tewes, Volkmann, 2002.
  3. Schmeichel, Mitchem, 1982.
  4. Li, Corneil, Mendelsohn, 2000, Proposition 2.5.
  5. Helden, 2007, Corollary 3.78.
  6. Bernhart, Kainen, 1979.
  7. Hakimi, Schmeichel, 1979.
  8. Skowrońska, 1985.
  9. Malkevitch, 1971.
  10. Harary, Moser, 1966, Corollary 5b.
  11. Harary, Moser, 1966, Theorem 7.
  12. Moon, 1966, Theorem 1.
  13. ↑ Alspach, 1967.
  14. Häggkvist, Thomassen, 1976, с. 20–40.
  15. Hobbs, (1976).
  16. Fleischner, 1976.
  17. Li, Corneil, Mendelsohn, 2000, Theorems 2.3 и 2.4.
  18. Underground, (1978).
  19. Harary, Moser, 1966.
  20. Moon, 1966.

Література ред.

  • Brian Alspach. Cycles of each length in regular tournaments // Canadian Mathematical Bulletin. — 1967. — Т. 10, вип. 2 (26 жовтня). — С. 283—286..
  • Frank Bernhart, Paul C. Kainen. The book thickness of a graph // Journal of Combinatorial Theory, Series B. — 1979. — Т. 27, вип. 3 (26 жовтня). — С. 320—331. — DOI:10.1016/0095-8956(79)90021-2..
  • J. A. Bondy. Pancyclic graphs I // Journal of Combinatorial Theory, Series B. — 1971. — Т. 11, вип. 1 (26 жовтня). — С. 80—84. — DOI:10.1016/0095-8956(71)90016-5..
  • H. Fleischner. In the square of graphs, Hamiltonicity and pancyclicity, Hamiltonian connectedness and panconnectedness are equivalent concepts // Monatshefte für Mathematik. — 1976. — Т. 82, вип. 2 (26 жовтня). — С. 125—149. — DOI:10.1007/BF01305995..
  • Roland Häggkvist, Carsten Thomassen. On pancyclic digraphs // Journal of Combinatorial Theory, Series B. — 1976. — Т. 20, вип. 1 (26 жовтня). — DOI:10.1016/0095-8956(76)90063-0..
  • S. L. Hakimi, E. F. Schmeichel. On the number of cycles of length k in a maximal planar graph // Journal of Graph Theory. — 1979. — Т. 3 (26 жовтня). — С. 69—86. — DOI:10.1002/jgt.3190030108..
  • Frank Harary, Leo Moser. The theory of round robin tournaments // American Mathematical Monthly. — 1966. — Т. 73, вип. 3 (26 жовтня). — С. 231—246. — DOI:10.2307/2315334..
  • Guido Helden. . — Rheinisch-Westfälischen Technischen Hochschule Aachen, 2007. — (Dissertation).
  • Arthur M. Hobbs. The square of a block is vertex pancyclic // Journal of Combinatorial Theory. — 1976. — Т. 20, вип. 1 (26 жовтня). — С. 1—4. — (Series B). — DOI:10.1016/0095-8956(76)90061-7..
  • Ming-Chu Li, Derek G. Corneil, Eric Mendelsohn. Pancyclicity and NP-completeness in planar graphs // Discrete Applied Mathematics. — 2000. — Т. 98, вип. 3 (26 жовтня). — С. 219—225. — DOI:10.1016/S0166-218X(99)00163-8..
  • Joseph Malkevitch. Recent Trends in Graph Theory. — Springer-Verlag, 1971. — Т. 186. — С. 191—195. — (Lecture Notes in Mathematics) — DOI:10.1007/BFb0059437..
  • J. W. Moon. On subtournaments of a tournament // Canadian Mathematical Bulletin. — 1966. — Т. 9, вип. 3 (26 жовтня). — С. 297—301. — DOI:10.4153/CMB-1966-038-7..
  • Bert Randerath, Ingo Schiermeyer, Meike Tewes, Lutz Volkmann. Vertex pancyclic graphs // Discrete Applied Mathematics. — 2002. — Т. 120, вип. 1—3 (26 жовтня). — С. 219—237. — DOI:10.1016/S0166-218X(01)00292-X..
  • Edward Schmeichel, John Mitchem. Bipartite graphs with cycles of all even lengths // Journal of Graph Theory. — 1982. — Т. 6, вип. 4 (26 жовтня). — С. 429—439. — DOI:10.1002/jgt.3190060407..
  • Mirosława Skowrońska. Cycles in Graphs / Brian R. Alspach, Christopher D. Godsil. — Elsevier Science Publishers B.V, 1985. — Т. 27. — С. 179—194. — (Annals of Discrete Mathematics).
  • Paris Underground. On graphs with Hamiltonian squares // Discrete Mathematics. — 1978. — Т. 21, вип. 3 (26 жовтня). — С. 323. — DOI:10.1016/0012-365X(78)90164-4..

Посилання ред.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Pancikli chnij graf oriyentovanij abo neoriyentovanij graf yakij mistit cikli vsih mozhlivih dovzhin vid troh do chisla vershin grafa 1 Panciklichni grafi ye uzagalnennyam gamiltonovih grafiv grafiv yaki mayut cikli najbilshoyi mozhlivoyi dovzhini Cikli vsih mozhlivih dovzhin u grafi oktaedr pokazuyut sho graf panciklichnij Zmist 1 Viznachennya 2 Planarni grafi 3 Turniri 4 Grafi z velikim chislom reber 5 Stepeni grafa 6 Obchislyuvalna skladnist 7 Istoriya 8 Primitki 9 Literatura 10 PosilannyaViznachennya red Graf G displaystyle G nbsp z n displaystyle n nbsp vershinami ye panciklichnim yaksho dlya bud yakogo k displaystyle k nbsp v mezhah 3 k n displaystyle 3 leqslant k leqslant n nbsp graf G displaystyle G nbsp mistit cikl dovzhini k displaystyle k nbsp 1 Graf ye vershinno panciklichnim yaksho dlya bud yakoyi vershini v displaystyle v nbsp i bud yakogo k displaystyle k nbsp v tih samih mezhah graf mistit cikl dovzhini k displaystyle k nbsp sho mistit vershinu v displaystyle v nbsp 2 Shozhim chinom graf ye reberno panciklichnim yaksho dlya bud yakogo rebra e displaystyle e nbsp i dlya bud yakogo k displaystyle k nbsp v tih samih mezhah vin mistit cikl dovzhini v displaystyle v nbsp sho mistit rebro e displaystyle e nbsp 2 Dvochastinnij graf ne mozhe buti panciklichnim oskilki vin ne mistit cikliv bud yakoyi neparnoyi dovzhini ale kazhut sho graf ye bipanciklichnim yaksho vin mistit cikli vsih parnih dovzhin vid 4 do n displaystyle n nbsp 3 Planarni grafi red Maksimalnij zovniplanarnij graf ce graf utvorenij iz prostogo mnogokutnika na ploshini shlyahom triangulyaciyi jogo vnutrishnosti Bud yakij maksimalnij zovniplanarnij graf ye panciklichnim sho mozhna pokazati indukciyeyu Zovnishnya gran grafa ye ciklom z n vershinami a vidalennya bud yakogo trikutnika z yednanogo iz reshtoyu grafa tilki odnim rebrom listok dereva yake utvoryuye dvoyistij graf triangulyaciyi utvoryuye maksimalnij zovniplanarnij graf z na odinicyu menshim chislom vershin a za indukcijnim pripushennyam cej graf maye vsi cikli vsih dovzhin sho zalishilisya Yaksho pridilyati bilshe uvagi viboru trikutnika dlya vidalennya to ti sami argumenti pokazuyut strogishij rezultat sho bud yakij maksimalnij zovniplanarnij graf ye vershinno panciklichnim 4 Te zh same istinne dlya grafiv yaki mayut maksimalnij zovniplanarnij graf yak kistyakovij pidgraf zokrema dlya kolesa Maksimalnij planarnij graf ce planarnij graf u yakomu vsi grani vklyuchno iz zovnishnoyu ye trikutnikami Maksimalnij planarnij graf ye vershinno panciklichnim todi j lishe todi koli vin mistit gamiltoniv cikl 5 yaksho vin ne gamiltoniv vin bezumovno ne panciklichnij a yaksho vin gamiltoniv to vnutrishnist gamiltonovogo ciklu utvoryuye zovnishnyu mezhu maksimalnogo zovnishplanarnogo grafa na tih samih vershinah i rebrah do yakoyi mozhna zastosuvati poperedni argumenti dlya zovniplanarnih grafiv 6 Napriklad na malyunku vgori pokazano panciklichnist grafa oktaedra gamiltonovogo maksimalnogo planarnogo grafa z shistma vershinami Strogishe z tih samih prichin yaksho maksimalnij planarnij graf maye cikl dovzhini k displaystyle k nbsp to vin maye cikli vsih menshih dovzhin 7 nbsp Majzhe panciklichnij graf Halina z ciklami vsih dovzhin azh do n za vinyatkom dovzhini 8Grafi Halina ye planarnimi grafami utvorenimi z planarnogo malyunka dereva yake maye vershin stepenya dva dodannyam ciklu sho z yednuye listki dereva Grafi Halina ne obov yazkovo panciklichni ale voni majzhe panciklichni v tomu sensi sho vidsutnij cikl maksimum odniyeyi dovzhini Dovzhina vidsutnogo ciklu obov yazkovo parna Yaksho zhodna zi vnutrishnih vershin grafa Halina ne maye stepenya tri to graf obov yazkovo panciklichnij 8 1971 roku pomicheno 1 sho bagato klasichnih umov dlya isnuvannya gamiltonovogo ciklu dostatni takozh dlya panciklichnosti tomu pripusheno sho bud yakij 4 zv yaznij planarnij graf panciklichnij ale nezabarom znajdeno simejstvo kontrprikladiv 9 Turniri red Turnir ce napryamlenij graf z odniyeyu napryamlenoyu dugoyu mizh bud yakoyu paroyu vershin Intuyitivno turnir mozhna vikoristati dlya modelyuvannya krugovoyi sistemi malyuvannyam dugi vid peremozhcya do peremozhenogo dlya kozhnoyi gri v zmaganni Turnir nazivayut silno zv yaznim abo prosto silnim todi j lishe todi koli jogo ne mozhna rozdiliti na dvi neporozhni pidmnozhini L displaystyle L nbsp i W displaystyle W nbsp tih hto prograv i vigrav tak sho bud yakij uchasnik W displaystyle W nbsp peremagaye bud yakogo uchasnika v L displaystyle L nbsp 10 Bud yakij silnij turnir ye panciklichnim 11 i vershinno panciklichnim 12 Yaksho turnir regulyarnij bud yakij uchasnik maye take zh chislo vigrashiv i prograshiv sho j inshi uchasniki to vin ye takozh reberno panciklichnim 13 odnak silni turniri z chotirma vershinami ne mozhut buti reberno panciklichnimi Grafi z velikim chislom reber red Teorema Mantelya stverdzhuye sho bud yakij neoriyentovanij graf iz n displaystyle n nbsp vershinami sho maye prinajmni n 2 4 displaystyle n 2 4 nbsp reber i ne maye kratnih reber i petel abo mistit trikutnik abo vin ye povnim dvochastinnim grafom K n 2 n 2 displaystyle K n 2 n 2 nbsp Cyu teoremu mozhna posiliti bud yakij neoriyentovanij gamiltoniv graf z ne mensh nizh n 2 4 displaystyle n 2 4 nbsp rebrami abo panciklichnij abo ce K n 2 n 2 displaystyle K n 2 n 2 nbsp 1 Isnuyut gamiltonovi oriyentovani grafi z n displaystyle n nbsp vershinami i z n n 1 2 3 displaystyle n n 1 2 3 nbsp dugami yaki ne ye panciklichnimi ale bud yakij gamiltoniv oriyentovanij graf prinajmni z n n 1 2 1 displaystyle n n 1 2 1 nbsp dugami panciklichnij Krim togo strogo zv yaznij graf z n displaystyle n nbsp vershinami v yakomu kozhna vershina maye stepin ne menshij vid n displaystyle n nbsp vhidni ta vihidni dugi rahuyutsya razom abo panciklichnij abo ye povnim dvochastinnim grafom 14 Stepeni grafa red Dlya bud yakogo grafa G displaystyle G nbsp jogo k displaystyle k nbsp j stepin grafa G k displaystyle G k nbsp viznachayetsya yak graf na tij samij mnozhini vershin sho maye rebro mizh bud yakimi dvoma vershinami vidstan mizh yakimi v G displaystyle G nbsp ne perevishuye k displaystyle k nbsp Yaksho G displaystyle G nbsp vershinno 2 zv yaznij to za teoremoyu Flyajshnera G 2 displaystyle G 2 nbsp ye gamiltonovim grafom Tverdzhennya mozhna posiliti graf obov yazkovo bude vershinno panciklichnim 15 Strogishe yaksho G 2 displaystyle G 2 nbsp ye gamiltonovim vin takozh i panciklichnij 16 Obchislyuvalna skladnist red Perevirka grafa na panciklichnist ye NP povnoyu zadacheyu navit dlya okremogo vipadku 3 zv yaznih kubichnih grafiv NP povnoyu zadacheyu ye takozh perevirka grafa na vershinnu panciklichnist navit dlya okrmogo vipadku poliedralnih grafiv 17 Takozh NP povnoyu zadacheyu ye perevirka kvadrata grafa na gamiltonovist a tim samim i perevirka na panciklichnist 18 Istoriya red Panciklichnist upershe doslidzhuvali Harari i Mozer u konteksti turniriv 19 a takozh Muun 20 i Alpach 13 Nazvu ponyattyu panciklichnosti dav Bondi yakij rozshiriv ponyattya dlya neoriyentovanih grafiv 1 Primitki red a b v g d Bondy 1971 a b Randerath Schiermeyer Tewes Volkmann 2002 Schmeichel Mitchem 1982 Li Corneil Mendelsohn 2000 Proposition 2 5 Helden 2007 Corollary 3 78 Bernhart Kainen 1979 Hakimi Schmeichel 1979 Skowronska 1985 Malkevitch 1971 Harary Moser 1966 Corollary 5b Harary Moser 1966 Theorem 7 Moon 1966 Theorem 1 a b Alspach 1967 Haggkvist Thomassen 1976 s 20 40 Hobbs 1976 Fleischner 1976 Li Corneil Mendelsohn 2000 Theorems 2 3 i 2 4 Underground 1978 Harary Moser 1966 Moon 1966 Literatura red Brian Alspach Cycles of each length in regular tournaments Canadian Mathematical Bulletin 1967 T 10 vip 2 26 zhovtnya S 283 286 Frank Bernhart Paul C Kainen The book thickness of a graph Journal of Combinatorial Theory Series B 1979 T 27 vip 3 26 zhovtnya S 320 331 DOI 10 1016 0095 8956 79 90021 2 J A Bondy Pancyclic graphs I Journal of Combinatorial Theory Series B 1971 T 11 vip 1 26 zhovtnya S 80 84 DOI 10 1016 0095 8956 71 90016 5 H Fleischner In the square of graphs Hamiltonicity and pancyclicity Hamiltonian connectedness and panconnectedness are equivalent concepts Monatshefte fur Mathematik 1976 T 82 vip 2 26 zhovtnya S 125 149 DOI 10 1007 BF01305995 Roland Haggkvist Carsten Thomassen On pancyclic digraphs Journal of Combinatorial Theory Series B 1976 T 20 vip 1 26 zhovtnya DOI 10 1016 0095 8956 76 90063 0 S L Hakimi E F Schmeichel On the number of cycles of length k in a maximal planar graph Journal of Graph Theory 1979 T 3 26 zhovtnya S 69 86 DOI 10 1002 jgt 3190030108 Frank Harary Leo Moser The theory of round robin tournaments American Mathematical Monthly 1966 T 73 vip 3 26 zhovtnya S 231 246 DOI 10 2307 2315334 Guido Helden Hamiltonicity of maximal planar graphs and planar triangulations Rheinisch Westfalischen Technischen Hochschule Aachen 2007 Dissertation Arthur M Hobbs The square of a block is vertex pancyclic Journal of Combinatorial Theory 1976 T 20 vip 1 26 zhovtnya S 1 4 Series B DOI 10 1016 0095 8956 76 90061 7 Ming Chu Li Derek G Corneil Eric Mendelsohn Pancyclicity and NP completeness in planar graphs Discrete Applied Mathematics 2000 T 98 vip 3 26 zhovtnya S 219 225 DOI 10 1016 S0166 218X 99 00163 8 Joseph Malkevitch Recent Trends in Graph Theory Springer Verlag 1971 T 186 S 191 195 Lecture Notes in Mathematics DOI 10 1007 BFb0059437 J W Moon On subtournaments of a tournament Canadian Mathematical Bulletin 1966 T 9 vip 3 26 zhovtnya S 297 301 DOI 10 4153 CMB 1966 038 7 Bert Randerath Ingo Schiermeyer Meike Tewes Lutz Volkmann Vertex pancyclic graphs Discrete Applied Mathematics 2002 T 120 vip 1 3 26 zhovtnya S 219 237 DOI 10 1016 S0166 218X 01 00292 X Edward Schmeichel John Mitchem Bipartite graphs with cycles of all even lengths Journal of Graph Theory 1982 T 6 vip 4 26 zhovtnya S 429 439 DOI 10 1002 jgt 3190060407 Miroslawa Skowronska Cycles in Graphs Brian R Alspach Christopher D Godsil Elsevier Science Publishers B V 1985 T 27 S 179 194 Annals of Discrete Mathematics Paris Underground On graphs with Hamiltonian squares Discrete Mathematics 1978 T 21 vip 3 26 zhovtnya S 323 DOI 10 1016 0012 365X 78 90164 4 Posilannya red Weisstein Eric W Panciklichnij graf angl na sajti Wolfram MathWorld Otrimano z https uk wikipedia org w index php title Panciklichnij graf amp oldid 37002129