однією з базових концепцій теорії графів і використовуються в багатьох математичних задачах та побудовах на графах. Кліки також вивчаються в інформатиці:...

розмальовка правильна. Розфарбовування графів Хроматичне число Кліка (теорія графів) Незалежна множина (теорія графів) Науково-популярний фізико-математичний...

визначення термінів із теорії графів. Курсивом позначені посилання на терміни в цьому словнику (на цій сторінці). Автоморфізм — ізоморфізм графа із самим собою...

Теорія графів — розділ математики, що вивчає властивості графів. Наочно граф можна уявити як геометричну конфігурацію, яка складається з точок (вершини)...

Екстремальна теорія графів — це гілка теорії графів. Екстремальна теорія графів вивчає екстремальні (максимальні або мінімальні) властивості графів, які задовольняють...

про кліку належить до класу NP-повних задач в області теорії графів. Вперше її сформулював 1972 року Річард Карп. Клікою в неорієнтованому графі називається...

Тобто це сума за 1-клікою цих повних графів. Граф має (k−1)n+1 вершин і nk(k−1)/2 ребер, обхват 3 (при k > 2), радіус 1 і діаметр 2. Граф має вершинну зв'язність...

циклу. Стиснуті графи можна утворити сумами за кліками хордальних графів і максимальних хордальних графів. Таким чином, стиснуті графи включають максимальні...

Вершиною в теорії графів називається базовий елемент, який використовується при побудові графа: неорієнтований граф складається з множини вершин і множини...

два графи G {\displaystyle G} і H {\displaystyle H} містять кліки однакового розміру, сума за клікою утворюється з незв'язаного об'єднання графів ототожненням...

У теорії графів деревна глибина зв'язного неорієнтованого графа G — це числовий інваріант G, мінімальна висота дерева Тремо для суперграфа графа G. Цей...

графів. Інші застосування цього поняття — доведення існування малих сепараторів у замкнутих за мінорами сімействах графів і опис країв і мінорів клік...

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

концепцій теорії графів стосуються одна одної через доповнення графів: Доповнення безреберного графа це повний граф і навпаки. Незалежна множина в графі це кліка...

чином, граф Турана не містить кліки розміру r + 1. Згідно з теоремою Турана, граф Турана має максимально можливе число ребер серед усіх графів без клік розміру...

У теорії графів розщеплюваним графом називають граф, у якому вершини можна розділити на кліку і незалежну множину. Розщеплювані графи вперше вивчали Фелдес...

Топологічна теорія графів — розділ теорії графів, що вивчає вкладення графів в поверхні, просторове вкладення і графи як топологічні простори. У цій галузі...

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

В теорії графів реберним графом L(G) неорієнтованого графа G називається граф L(G), що представляє сусідство ребер графа G. Поняття реберного графа для...

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

початковий граф такого ребра не має. Таким чином, кліка у початковому графі стає незалежною множиною в доповненні і розфарбування початкового графа стає кліковим...

контексті скінченних графів, початковою метою Ердеша та Хайнала була теорія нескінченних графів. Число розфарбовування для нескінченного графа G можна визначити...

В теорії графів деревна ширина неорієнтованого графу — це число, асоційоване з графом. Деревну ширину можна визначити декількома еквівалентними способами:...

У теорії графів шляхова декомпозиція графа G — це, неформально, подання графа G у вигляді «потовщеного» шляху, а шляхова ширина графа G — це число, що...

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

В теорії графів кограф, або додатково звідний граф, чи граф, вільний від P4, — це граф, який можна отримати з графа з єдиною вершиною K1 операціями доповнення...

теорії графів суміжною вершиною вершини v називається вершина, поєднана з v ребром. Околом вершини v в графі G називається породжений підграф графа G...

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

У теорії графів графом без клешень називається граф, який не містить клешень, як породжених підграфів. Клешнею називається повний двочастковий граф K1...

«Екстремальна теорія графів»). Такі графи є чудовими спектральними експандерами. Прикладами графів Рамануджана є кліки, повні двочасткові графи K n , n {\displaystyle...

Структурна теорема графів — фундаментальний результат у теорії графів. Результат встановлює тісний зв'язок між теорією мінорів графів і топологічними вкладеннями...