www.wikidata.uk-ua.nina.az

Добуток графів це бінарна операція на графах Конкретніше це операція яка двом графам G1 і G2 ставить у відповідність гра

Добуток графів

Добуток графів - це бінарна операція на графах. Конкретніше, це операція, яка двом графам G1 і G2 ставить у відповідність граф H з такими властивостями:

Види добутків Редагувати

У таблиці наведено найуживаніші добутки графів. Позначення: означає «з'єднані ребром» і означає «не з'єднані ребром». Символи операцій, наведені нижче, не завжди стандартизовані, особливо в ранніх роботах.

Назва Умова для (, ) ∼ (, ) Розміри Приклад
Декартів добуток
 (  =  і    )
або

(    і  =  )

Тензорний добуток
(категорійний добуток)
    і   
Лексикографічний добуток
або 		u1 ∼ v1
або
( u1 = v1 і u2 ∼ v2 )
Сильний добуток
(нормальний добуток)
 ( u1 = v1 і u2 ∼ v2 )
або
( u1 ∼ v1 і u2 = v2 )
або
( u1 ∼ v1 і u2 ∼ v2 )
Конормальний добуток
(диз'юнктний добуток)
 u1 ∼ v1
або
u2 ∼ v2
Модулярний добуток[en] і
або
і
Кореневий добуток див. статтю
Добуток Кронекера див. статтю див. статтю див. статтю
Зигзаг-добуток див. статтю див. статтю див. статтю
Замінювальний добуток[en]
Гомоморфний добуток
або
і

У загальному випадку добуток графів визначається будь-якою умовою для (u1, u2) ∼ (v1, v2), яку можна виразити в термінах тверджень u1 ∼ v1, u2 ∼ v2, u1 = v1 і u2 = v2.

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

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

Нотація для лексикографічного добутку нагадує, що добуток не комутативний.

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

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

  1. David E. Roberson, Laura Mancinska. Graph Homomorphisms for Quantum Players. — 2012. — 14 вересня.
  2. R. Bačík, S. Mahajan. Computing and Combinatorics. — 1995. — Т. 959. — С. 566, Semidefinite programming and its applications to NP problems. — (Lecture Notes in Computer Science) — ISBN 3-540-60216-X. — DOI:10.1007/BFb0030878.

Література Редагувати

  • Imrich, Wilfried; Klavžar, Sandi. Product Graphs: Structure and Recognition. — Wiley, 2000. — ISBN 0-471-37039-8..
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Dobutok grafiv ce binarna operaciya na grafah Konkretnishe ce operaciya yaka dvom grafam G1 i G2 stavit u vidpovidnist graf H z takimi vlastivostyami Mnozhina vershin grafu H ce pryamij dobutok V G1 V G2 de V G1 i V G2 ye mnozhinami vershin G1 i G2 vidpovidno Dvi vershini u1 u2 i v1 v2 grafu H z yednani rebrom todi i tilki todi koli vershini u1 u2 v1 v2 zadovolnyayut pevnim umovam sho vidpovidayut tipu dobutku div nizhche Zmist 1 Vidi dobutkiv 2 Mnemonika 3 Div takozh 4 Primitki 5 LiteraturaVidi dobutkiv RedaguvatiU tablici navedeno najuzhivanishi dobutki grafiv Poznachennya displaystyle sim nbsp oznachaye z yednani rebrom i displaystyle not sim nbsp oznachaye ne z yednani rebrom Simvoli operacij navedeni nizhche ne zavzhdi standartizovani osoblivo v rannih robotah Nazva Umova dlya u 1 displaystyle u 1 nbsp u 2 displaystyle u 2 nbsp v 1 displaystyle v 1 nbsp v 2 displaystyle v 2 nbsp Rozmiri PrikladDekartiv dobutokG H displaystyle G square H nbsp u 1 displaystyle u 1 nbsp v 1 displaystyle v 1 nbsp i u 2 displaystyle u 2 nbsp displaystyle sim nbsp v 2 displaystyle v 2 nbsp abo u 1 displaystyle u 1 nbsp displaystyle sim nbsp v 1 displaystyle v 1 nbsp i u 2 displaystyle u 2 nbsp v 2 displaystyle v 2 nbsp G V 1 E 1 H V 2 E 2 J V 1 V 2 E 2 V 1 E 1 V 2 displaystyle G V 1 E 1 square H V 2 E 2 rightarrow J V 1 V 2 E 2 V 1 E 1 V 2 nbsp nbsp Tenzornij dobutok kategorijnij dobutok G H displaystyle G times H nbsp u 1 displaystyle u 1 nbsp displaystyle sim nbsp v 1 displaystyle v 1 nbsp i u 2 displaystyle u 2 nbsp displaystyle sim nbsp v 2 displaystyle v 2 nbsp G V 1 E 1 H V 2 E 2 J V 1 V 2 2 E 1 E 2 displaystyle G V 1 E 1 times H V 2 E 2 rightarrow J V 1 V 2 2E 1 E 2 nbsp nbsp Leksikografichnij dobutokG H displaystyle G cdot H nbsp abo G H displaystyle G H nbsp u1 v1abo u1 v1 i u2 v2 G V 1 E 1 H V 2 E 2 J V 1 V 2 E 2 V 1 E 1 V 2 2 displaystyle G V 1 E 1 cdot H V 2 E 2 rightarrow J V 1 V 2 E 2 V 1 E 1 V 2 2 nbsp nbsp Silnij dobutok normalnij dobutok G H displaystyle G boxtimes H nbsp u1 v1 i u2 v2 abo u1 v1 i u2 v2 abo u1 v1 i u2 v2 G V 1 E 1 H V 2 E 2 J V 1 V 2 V 1 E 2 V 2 E 1 2 E 1 E 2 displaystyle G V 1 E 1 boxtimes H V 2 E 2 rightarrow J V 1 V 2 V 1 E 2 V 2 E 1 2E 1 E 2 nbsp Konormalnij dobutok diz yunktnij dobutok G H displaystyle G H nbsp u1 v1abou2 v2Modulyarnij dobutok en u 1 v 1 displaystyle u 1 sim v 1 nbsp i u 2 v 2 displaystyle u 2 sim v 2 nbsp abo u 1 v 1 displaystyle u 1 not sim v 1 nbsp i u 2 v 2 displaystyle u 2 not sim v 2 nbsp Korenevij dobutok div stattyu G V 1 E 1 H V 2 E 2 J V 1 V 2 E 2 V 1 E 1 displaystyle G V 1 E 1 cdot H V 2 E 2 rightarrow J V 1 V 2 E 2 V 1 E 1 nbsp nbsp Dobutok Kronekera div stattyu div stattyu div stattyuZigzag dobutok div stattyu div stattyu div stattyuZaminyuvalnij dobutok en Gomomorfnij dobutok 1 2 G H displaystyle G ltimes H nbsp u 1 v 1 displaystyle u 1 v 1 nbsp abo u 1 v 1 displaystyle u 1 sim v 1 nbsp i u 2 v 2 displaystyle u 2 not sim v 2 nbsp U zagalnomu vipadku dobutok grafiv viznachayetsya bud yakoyu umovoyu dlya u1 u2 v1 v2 yaku mozhna viraziti v terminah tverdzhen u1 v1 u2 v2 u1 v1 i u2 v2 Mnemonika RedaguvatiNehaj K 2 displaystyle K 2 nbsp povnij graf z dvoma vershinami tobto odne rebro Dobutki grafiv K 2 K 2 displaystyle K 2 square K 2 nbsp K 2 K 2 displaystyle K 2 times K 2 nbsp i K 2 K 2 displaystyle K 2 boxtimes K 2 nbsp viglyadayut tak yak znak operaciyi mnozhennya Napriklad K 2 K 2 displaystyle K 2 square K 2 nbsp ye ciklom dovzhini 4 kvadrat a K 2 K 2 displaystyle K 2 boxtimes K 2 nbsp ye povnim grafom z chotirma vershinami Notaciya G H displaystyle G H nbsp dlya leksikografichnogo dobutku nagaduye sho dobutok ne komutativnij Div takozh RedaguvatiOperaciyi nad grafamiPrimitki Redaguvati David E Roberson Laura Mancinska Graph Homomorphisms for Quantum Players 2012 14 veresnya R Bacik S Mahajan Computing and Combinatorics 1995 T 959 S 566 Semidefinite programming and its applications to NP problems Lecture Notes in Computer Science ISBN 3 540 60216 X DOI 10 1007 BFb0030878 Literatura RedaguvatiImrich Wilfried Klavzar Sandi Product Graphs Structure and Recognition Wiley 2000 ISBN 0 471 37039 8 Otrimano z https uk wikipedia org w index php title Dobutok grafiv amp oldid 32820961