www.wikidata.uk-ua.nina.az

Мультиграф В теорії графів мультиграфом або псевдографом називають граф в якому допускається наявність кратних ребер їх

Мультиграф

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

Мультиграф з кратними ребрами (червоні) і петлями (сині). Не всі автори дозволяють мультиграфам мати петлі.

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

Неорієнтовані мультиграфи (ребра без власної ідентифікації) Редагувати

Формально, мультиграфом G називають впорядковану пару  G:=(V, E), в якій

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

Деякі автори дозволяють мультиграфам мати петлі, тобто ребра, які з'єднують вершину саму з собою, інші називають такі графи псевдографами, а термін мультиграф залишають для графів без петель.

Орієнтовані мультиграфи (ребра без власної ідентифікації) Редагувати

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

Мультиорграфом G називається впорядкована пара G:=(V,A), в якій

  • V — множина вершин,
  • A — мультимножина впорядкованих пар вершин. Елементи цієї множини називають дугами.

Змішаний мультиграф G:=(V,E, A) можна визначити таким же чином, як і змішаний граф.

Орієнтовані мультиграфи (ребра з власною ідентифікацією) Редагувати

Мультиорграфом G називають впорядковану четвірку G:=(V, A, s, t), в якій

  • V — множина вершин,
  • A — множина дуг,
  • призначає кожній дузі початкову вершину,
  • призначає кожній дузі кінцеву вершину.

В теорії категорій невеликі категорії можуть бути визначені як мультиорграфи (з дугами, які мають власну ідентифікацію), оснащені законом побудови і петлями для кожної вершини, які служать лівою і правою ідентифікацією для побудови. У зв'язку з цим в теорії категорій під терміном граф зазвичай розуміють «мультиорграф», мультиорграф який лежить в основі категорії називається базовим  орграфом.

Розмітка Редагувати

Мультиграфи і мультиорграфи підтримують поняття розмітки однаково, однак в цьому випадку немає єдності термінології.

Визначення помічені мультиграфи і помічені мультиорграфи схожі, тому тут вкажемо визначення тільки для мультиорграфу.

Визначення 1: Помічений мультиорграф — це помічений граф з мітками на дугах і вершинах.

Формально: Помічений мультиорграф G — це кортеж з 8 елементів , в якому 

  • V — множина вершин і A — множина дуг,
  • і — кінцевий алфавіт, доступний для розмітки дуг і вершин,
  • і — два відображення, які визначають початкову і кінцеву вершини дуги,
  • і — два відображення, які описують розмітку вершин і дуг.

Визначення 2: Помічений мультиорграф — помічений орграф з кратними поміченими дугами, тобто дугами з тими ж кінцями і тими ж мітками (це відрізняється від поняття, даного в статті «Розмітка графу»).

Див. також Редагувати

Примітки Редагувати

Посилання Редагувати

  • Béla Bollobás. Modern Graph Theory. — Springer, 2002. — ISBN 0-387-98488-7.
  • V. K. Balakrishnan. Graph Theory. — McGraw-Hill, 1997. — ISBN 0-07-005489-4.
  • Рейнгард Дистель. Теория графов. — Новосибирск: Изд-во Ин-та математики, 2002. — ISBN 5-86134-101-Х.
  • Jonathan L Gross, Jay Yellen. Graph Theory and Its Applications. — McGraw-Hill, 1998. — ISBN 0-8493-3982-0.
  • Jonathan L Gross, Jay Yellen. Handbook of Graph Theory. — McGraw-Hill, 2003. — ISBN 1-58488-090-2.
  • Ф.Харари. Теория графов. — Москва: Едиториал УРСС, 2003. — ISBN 5-354-00301-6.
  • Daniel Zwillinger. CRC Standard Mathematical Tables and Formulae. — Chapman & Hall/CRC, 2002. — ISBN 1-58488-291-3.
  • Svante Janson, Donald E. Knuth, Tomasz Luczak, Boris Pittel The birth of the giant component // Random Structures and Algorithms. — 1993. — Т. 4, вып. 3. — С. 231—358. — DOI:10.1002/rsa.3240040303.

Зовнішні посилання Редагувати

  • Paul E. Black, Multigraph at the NIST Dictionary of Algorithms and Data Structures.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
V teoriyi grafiv multigrafom abo psevdografom nazivayut graf v yakomu dopuskayetsya nayavnist kratnih reber yih takozh nazivayut paralelnimi tobto ye rebra yaki mayut odni j ti zh kincevi vershini Takim chinom dvi vershini mozhut buti z yednani bilsh nizh odnim rebrom cim multigrafi vidriznyayutsya vid gipergrafiv v yakih kozhne rebro mozhe z yednuvati bud yake chislo vershin a ne rivno dvi Multigraf z kratnimi rebrami chervoni i petlyami sini Ne vsi avtori dozvolyayut multigrafam mati petli Isnuye dva metodi poznachennya reber multigrafu Deyaki govoryat sho yak i v vipadku grafiv bez kratnih reber rebro viznachayetsya vershinami yaki vono z yednuye ale kozhne rebro mozhe povtoryuvatisya dekilka raziv Inshi viznachayut rebra rivnopravnimi z vershinami elementami grafu i voni povinni mati vlasnu identifikaciyu Zmist 1 Neoriyentovani multigrafi rebra bez vlasnoyi identifikaciyi 2 Oriyentovani multigrafi rebra bez vlasnoyi identifikaciyi 3 Oriyentovani multigrafi rebra z vlasnoyu identifikaciyeyu 4 Rozmitka 5 Div takozh 6 Primitki 7 Posilannya 8 Zovnishni posilannyaNeoriyentovani multigrafi rebra bez vlasnoyi identifikaciyi RedaguvatiFormalno multigrafom G nazivayut vporyadkovanu paru G V E v yakij V mnozhina vershin E multimnozhina nevporyadkovanih par vershin Elementi ciyeyi mnozhini nazivayutsya rebrami Multigrafi mozhna vikoristovuvati dlya podavannya mozhlivih povitryanih shlyahiv litaka V comu vipadku multigraf staye oriyentovanim i para oriyentovanih paralelnih reber yaki zv yazuyut mista pokazuye sho mozhna letiti v oboh napryamkah z mista abo v misto Deyaki avtori dozvolyayut multigrafam mati petli tobto rebra yaki z yednuyut vershinu samu z soboyu inshi nazivayut taki grafi psevdografami a termin multigraf zalishayut dlya grafiv bez petel Oriyentovani multigrafi rebra bez vlasnoyi identifikaciyi RedaguvatiMultiorgraf ce oriyentovanij graf v yakomu dopustimi kratni dugi tobto ye dugi yaki mayut odnakovi pochatkovi i kincevi vershini Multiorgrafom G nazivayetsya vporyadkovana para G V A v yakij V mnozhina vershin A multimnozhina vporyadkovanih par vershin Elementi ciyeyi mnozhini nazivayut dugami Zmishanij multigraf G V E A mozhna viznachiti takim zhe chinom yak i zmishanij graf Oriyentovani multigrafi rebra z vlasnoyu identifikaciyeyu RedaguvatiMultiorgrafom G nazivayut vporyadkovanu chetvirku G V A s t v yakij V mnozhina vershin A mnozhina dug s A V displaystyle s A rightarrow V nbsp priznachaye kozhnij duzi pochatkovu vershinu t A V displaystyle t A rightarrow V nbsp priznachaye kozhnij duzi kincevu vershinu V teoriyi kategorij neveliki kategoriyi mozhut buti viznacheni yak multiorgrafi z dugami yaki mayut vlasnu identifikaciyu osnasheni zakonom pobudovi i petlyami dlya kozhnoyi vershini yaki sluzhat livoyu i pravoyu identifikaciyeyu dlya pobudovi U zv yazku z cim v teoriyi kategorij pid terminom graf zazvichaj rozumiyut multiorgraf multiorgraf yakij lezhit v osnovi kategoriyi nazivayetsya bazovim orgrafom Rozmitka RedaguvatiMultigrafi i multiorgrafi pidtrimuyut ponyattya rozmitki odnakovo odnak v comu vipadku nemaye yednosti terminologiyi Viznachennya pomicheni multigrafi i pomicheni multiorgrafi shozhi tomu tut vkazhemo viznachennya tilki dlya multiorgrafu Viznachennya 1 Pomichenij multiorgraf ce pomichenij graf z mitkami na dugah i vershinah Formalno Pomichenij multiorgraf G ce kortezh z 8 elementiv G S V S A V A s t ℓ V ℓ A displaystyle G Sigma V Sigma A V A s t ell V ell A nbsp v yakomu V mnozhina vershin i A mnozhina dug S V displaystyle Sigma V nbsp i S A displaystyle Sigma A nbsp kincevij alfavit dostupnij dlya rozmitki dug i vershin s A V displaystyle s colon A rightarrow V nbsp i t A V displaystyle t colon A rightarrow V nbsp dva vidobrazhennya yaki viznachayut pochatkovu i kincevu vershini dugi ℓ V V S V displaystyle ell V colon V rightarrow Sigma V nbsp i ℓ A A S A displaystyle ell A colon A rightarrow Sigma A nbsp dva vidobrazhennya yaki opisuyut rozmitku vershin i dug Viznachennya 2 Pomichenij multiorgraf pomichenij orgraf z kratnimi pomichenimi dugami tobto dugami z timi zh kincyami i timi zh mitkami ce vidriznyayetsya vid ponyattya danogo v statti Rozmitka grafu Div takozh RedaguvatiSlovnik terminiv teoriyi grafiv Teoriya grafivPrimitki RedaguvatiPosilannya RedaguvatiBela Bollobas Modern Graph Theory Springer 2002 ISBN 0 387 98488 7 V K Balakrishnan Graph Theory McGraw Hill 1997 ISBN 0 07 005489 4 Rejngard Distel Teoriya grafov Novosibirsk Izd vo In ta matematiki 2002 ISBN 5 86134 101 H Jonathan L Gross Jay Yellen Graph Theory and Its Applications McGraw Hill 1998 ISBN 0 8493 3982 0 Jonathan L Gross Jay Yellen Handbook of Graph Theory McGraw Hill 2003 ISBN 1 58488 090 2 F Harari Teoriya grafov Moskva Editorial URSS 2003 ISBN 5 354 00301 6 Daniel Zwillinger CRC Standard Mathematical Tables and Formulae Chapman amp Hall CRC 2002 ISBN 1 58488 291 3 Svante Janson Donald E Knuth Tomasz Luczak Boris Pittel The birth of the giant component Random Structures and Algorithms 1993 T 4 vyp 3 S 231 358 DOI 10 1002 rsa 3240040303 Zovnishni posilannya RedaguvatiPaul E Black Multigraph at the NIST Dictionary of Algorithms and Data Structures Otrimano z https uk wikipedia org w index php title Multigraf amp oldid 35785252