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

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

Vertalings in die woordeboek Russies - Hongaars

páros gráf

Soortgelyke frases

Полный двудольный граф
Teljes páros gráf

voorbeelde

Следовательно, любой двудольный граф с обхватом по меньшей мере шесть можно рассматривать как граф Леви абстрактной структуры инцидентности.
Megfordítva, bármely, legalább 6 girthű páros gráf tekinthető egy absztrakt illeszkedési struktúra Levi-gráfjának.

Двудольным двойным покрытием полного графа 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.

Поэтому минимальное вершинное покрытие может быть найдено с помощью алгоритма нахождения паросочетаний в двудольных графах.
Ezért a minimális csúcslefedés megtalálható a páros gráf párosítási algoritmusával.

В примере выше четыре верхних вершины порождают клешню (то есть, полный двудольный граф 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.

Этот результат можно рассматривать как простой эквивалент теоремы Кёнига, значительно более ранний результат относительно паросочетаний и вершинных покрытий в двудольных графах.
Ez az eredmény egyenértékűnek tekinthető a Kőnig-tétellel, ami egy sokkal korábbi eredmény a párosításokkal és csúcsfedésekkel kapcsolatban páros gráfokban.

Кроме полных графов с числом вершин меньше 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.

Поскольку рёберная раскраска двудольного графа может быть выполнена за полиномиальное время, то это же верно и для указанного специального случая расписания для открытой линии.
Mivel a páros élszínezés polinom időben elvégezhető, ugyanez igaz az open-shop ütemezés ezen korlátozott esetére.

С этой точки зрения ребро двудольного графа, соединяющее вершину i одной стороны с вершиной j другой стороны, соответствует клетке шахматной доски с координатами (i,j).
Így tekintve, a teljes páros gráf egy éle, ami a bipartíció egyik oldalának i-edik csúcsa és a bipartíció másik oldalának j-edik csúcsa között húzódik, egy sakktábla (i, j) koordinátájú mezőjének felel meg.

Задача определения ахроматического числа остаётся 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.

Все другие точки остаются #P-трудными даже для двудольных планарных графов.
Kiszámítása #P-teljes probléma, még páros gráfokra is.

Невозможно использовать теорему Гринберга для поиска контрпримеров гипотезе Барнетта, что любой кубический двудольный полиэдральный граф гамильтонов.
Nem használható a Grinberg-tétel a Barnette-sejtés ellenpéldáinak kereséséhez sem; Barnette sejtése szerint minden 3-reguláris páros poliédergráfnak van Hamilton-köre.

Например, у линейных лесов (компоненты которых являются двудольными графами) инвариант равняется 1; у внешнепланарных графов инвариант равняется 2, и они могут быть раскрашены тремя цветами; у планарных графов инвариант — 3, и они могут быть раскрашены четырьмя цветами.
Például a lineáris erdők invariánsa 1, és 2-színezhetők; a külsíkgráfok invariánsa kettő, és 3-színezhetők, és a síkbarajzolható gráfok (a négyszíntétel értelmében) 4-színezhetők.

Пусть A — множество элементов S, которым не соответствует никакая вершина в C. Тогда A имеет как минимум n — m элементов (возможно больше, если C содержит вершины, соответствующие одному и тому же элементу на обоих сторонах двудольного графа).
Legyen A S azon elemeinek a halmaza, melyek nem felelnek meg C egyik csúcsának sem; ekkor A legalább n − m elemmel rendelkezik (többel is rendelkezhet, ha a C tartalmaz a párosítás mindkét oldalának megfelelő elemeket).

Фёлдес и ХаммерFöldes, Hammer, 1977a дали более общее определение, в котором графы, которые они называют расщепляемыми, включают также двудольные графы (то есть, графы, разбитые на два независимых множества) и дополнения двудольных графов (то есть, графы, которые можно разложить на две клики).
(Földes & Hammer 1977a) általánosabb definíciója szerint a split gráfoknak nevezett gráfok közé tartoznak a páros gráfok is (tehát a két független csúcshalmazba particionálható gráfok), továbbá a páros gráfok komplementerei (tehát a két klikkbe particionálható gráfok) is.

Задача остаётся #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).

Таким образом, семейство псевдолесов замкнуто по минорам, а из теоремы Робертсона — Сеймура тогда следует, что псевдолеса можно описать в терминах конечного набора запрещённых миноров, аналогично теореме Вагнера описания планарных графов как графов, не имеющих ни полного графа 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.

Двудольным двойным покрытием графа Петерсена является граф Дезарга — K2 × G(5,2)=G(10,3).
A Petersen-gráf páros dupla fedése a Desargues-gráf: K2 × G(5,2) = G(10,3).

Тесно связанная декомпозиция используется для визуализации графов Эпштейном, Гудрихом и Менгом (Eppstein, Goodrich, Meng (2006)) и (для двудольных дистанционно-наследуемых графов) Хуэем, Шефером и Штефанковичем (Hui, Schaefer, Štefankovič (2004)).
Egy hasonló felbontási módszert gráf lerajzolásához használt (Eppstein, Goodrich & Meng 2006), páros távolság-örökletes gráfokhoz pedig (Hui, Schaefer & Štefankovič 2004).