Що таке ідеальний збіг на графіку?
У теорії графів ідеальний
на графіку є відповідність, яка охоплює кожну вершину графа. Формальніше кажучи, заданий граф G = (V, E), ідеальний відповідник у G — це підмножина M множини ребер E, така що кожна вершина множини вершин V суміжна точно з одним ребром у M.
Граф G ідеальний, якщо для кожного індукованого підграфа H графа G χ(H) = ω(H). Дірка в графі — це безхордовий цикл довжиною понад 3, який буває парним або непарним залежно від кількості вершин, які він містить. Антидіра є доповненням до діри.
Дано граф G = (V, E), відповідність M у G є набором попарно несуміжних ребер, жодне з яких не є петлею; тобто ніякі два ребра не мають спільних вершин. Вершина є зіставленою (або насиченою), якщо вона є кінцевою точкою одного з ребер у зіставленні. Інакше вершина буде незрівняною (або ненасиченою).
3-регулярний граф має ідеальний збіг. Ми називаємо ребро мостом, якщо його видалення збільшує кількість зв’язаних компонентів.
Ідеальний код C у графі Γ є незалежний набір вершин Γ такий, що кожна вершина поза C є суміжною з єдиною вершиною в C, а повний досконалий код C у Γ — це набір вершин Γ, такий, що кожна вершина Γ є суміжною з єдиною вершиною в C.
У теорії графів ідеальним збігом у графі є відповідність, яка охоплює кожну вершину графа. Формальніше кажучи, заданий граф G = (V, E), ідеальний відповідник у G — це підмножина M множини ребер E, така що кожна вершина множини вершин V суміжна точно з одним ребром у M.