Полный двудольный граф oor Hongaars

Полный двудольный граф

Vertalings in die woordeboek Russies - Hongaars

Teljes páros gráf

voorbeelde

Двудольным двойным покрытием полного графа Kn является корона (полный двудольный граф Kn,n минус совершенное паросочетание).
Egy Kn teljes gráf páros dupla fedése koronagráf (egy Kn,n teljes páros gráf mínusz egy teljes párosítás).

Клешнёй называется полный двудольный граф K1,3 (то есть звезда с тремя рёбрами, тремя листьями и одной центральной вершиной).
A karom a K1,3 teljes páros gráf másik neve (tehát arról a csillaggráfról van szó, ami három éllel, három levéllel és egy csomóponttal rendelkezik).

Наименьшие кубические графы с числом пересечений 1 — полный двудольный граф K3,3 с 6 вершинами.
Az 1 metszési számúak közül a legkisebb a K3,3 teljes páros gráf, 6 csúcsponttal.

Полная классификация 1-планарных полных графов, полных двудольных графов и более общих полных многодольных графов известна.
Az 1-síkbarajzolható teljes gráfok, teljes páros gráfok és általánosabban a teljes többrészes gráfok teljes osztályozása ismeretes.

В примере выше четыре верхних вершины порождают клешню (то есть, полный двудольный граф K1,3), показанный вверху слева иллюстрации запрещённых подграфов.
A fenti példában a négy felső csúcs tartalmazza a karmot (tehát a K1,3 teljes páros gráfot), amely a tiltott gráfok illusztrációi közül a bal felső az ábrán.

Это графы, которые могут быть полностью разложены на клики и звёзды (полные двудольные графы K1,q) с помощью расщепляющей декомпозиции.
Azok a gráfok, melyek feloszthatók klikkekre és csillagokra (K1,q teljes páros gráfokra) splitfelbontással.

Кроме полных графов с числом вершин меньше 3 и всех полных двудольных графов семь приведённых выше — это все известные графы этого вида.
A 3-nál kevesebb csúcsú teljes gráfokon és az összes teljes páros gráfon kívül csak a fenti listában szereplő hét gráf ismert közülük.

Комплекс паросочетаний полного двудольного графа называется комплексом шахматной доски, так как его можно описать как комплекс множеств взаимно неатакующих ладей на шахматной доске.
Egy teljes páros gráf párosítási komplexusát „sakktáblakomplexusnak” (chessboard complex) is nevezik, mivel leírható egy sakktáblán egymást nem támadó bástyák halmazai komplexusaként.

Например, полный двудольный граф K1,n имеет тот же рёберныё граф, что и дипольный граф и мультиграф Шеннона с тем же числом рёбер.
Például a K1,n teljes páros gráfnak ugyanaz az élgráfja, mint az ugyanannyi éllel rendelkező dipólusgráfnak és a Shannon-multigráfnak.

Таким образом, семейство псевдолесов замкнуто по минорам, а из теоремы Робертсона — Сеймура тогда следует, что псевдолеса можно описать в терминах конечного набора запрещённых миноров, аналогично теореме Вагнера описания планарных графов как графов, не имеющих ни полного графа K5, ни полного двудольного графа K3,3 в качестве миноров.
Ezért a pszeudoerdők családja a minorképzés műveletére nézve zárt, és a Robertson–Seymour-tétel alapján a pszeudoerdők jellemezhetők tiltott minorjaik véges halmaza alapján, ahogy a Wagner-tétel karakterizálja a síkbarajzolható gráfokat, mint a sem a K5 teljes gráfot, sem a K3,3 teljes páros gráfot minorként nem tartalmazó gráfokat.

В обратную сторону, если семейство графов определено запрещёнными подграфами или замкнуто по отношению к операции взятия подграфа и не включает плотные графы произвольно большого размера, оно должно быть свободным от t-биклик для некоторого t, в противном случае, семейство должно включать произвольно большие плотные полные двудольные графы.
Megfordítva, ha egy gráfcsaládot tiltott részgráfjai alapján határozunk meg, illetve a részgráfképzés műveletére nézve zárt és nem tartalmaz tetszőlegesen nagyméretű sűrű gráfokat, akkor szükségképpen t-biklikkmentes valamely t értékre, különben nagy, sűrű teljes páros gráfokat kellene tartalmaznia.

Задача остаётся #P-полной в специальном случае перечисления совершенных паросочетаний в двудольном графе, поскольку вычисление перманента случайной 0-1 матрицы (другая #P-полная задача) — это то же самое, что вычисление числа совершенных паросочетаний в двудольном графе, имеющем заданную матрицу в качестве матрицы смежности.
A teljes párosítások leszámlálása is #P-teljes, még páros gráfokban is, mivel egy tetszőleges 0–1 mátrix permanensének kiszámítása (egy másik #P-teljes probléma) megegyezik egy olyan páros gráf teljes párosításainak leszámlálásával, melynek adott mátrix a páros-szomszédsági mátrixa (biadjacency matrix).

Как заметил Сеймур (Seymour 2006), любой граф сравнимости, не являющийся ни полным, ни двудольным, имеет косое разложение.
(Seymour 2006) alapján minden olyan összehasonlíthatósági gráf, ami se nem teljes gráf, se nem páros gráf, rendelkezik ferde partícióval.

Задача определения ахроматического числа остаётся NP-полной также для некоторых специальных классов графов: двудольные графы, дополнения двудольных графов (то есть, графы, не имеющие независимого множества с более чем двумя вершинами), кографы, интервальные графы и даже деревья.
Az akromatikus szám problémájának NP-teljessége még néhány speciális gráfosztályra igaz, ezek közé tartoznak: a páros gráfok, a páros gráfok komplementerei (tehát a két csúcsnál nagyobb független halmazzal nem rendelkező gráfok), a kográfok és az intervallumgráfok, és még a fák is.