теорія-графів - Зв’язкові графи
У графі $%2n$% вершин, ступінь кожної дорівнює $%n$%. Доведіть, що після видалення будь-якого підмножини з менш ніж $%n$% ребер виходить зв'язковий граф.
Моє рішення: Для початку доведемо, що після видалення $%n - 1$% ребер, у нас їх взагалі залишається достатньо, щоб граф був зв'язковим. По лемі: сума ступенів всіх вершин графа дорівнює $%2*E$% ($%E$% - у ребер), отримуємо $%2n^2 = 2E$%, звідси випливає, що $%E = n ^ 2 $ %. За теоремою "У зв'язному графі з $%N$% вершинами не менше $%N - 1$% ребер" отримуємо, що $%n^2 - (n - 1) \geq 2n - 1$%. (т.к. вершин у нас $% 2n $ %, значить ребер має бути не менше $ % 2n - 1 $ %). Перетворюємо нерівність і одержуємо $%\to (n - 1)^2 \geq n - 1$%, що є, безсумнівно, правильно.
Далі доведемо, що жодну вершину не можна від'єднати від графа. Так як кожна вершина пов'язана з рештою графа $%n$% ребрами, значить, при видаленні $%n - 1$% ребер, вершина так само залишиться пов'язана з рештою графа як мінімум одним ребром. Значить, граф залишиться зв'язковим, що потрібно було довести.
Я правильно все довів?
заданий18 Лис '14 18:46
Leva319 1.7k ● 1 ● 6 ● 41 77% прийнятих
Насамперед, граф із умови завдання має вважатися простим: інакше твердження нічого очікувати правильно. Я так розумію, що в більшості завдань цього роду таке припущення робиться "за умовчанням".
Поняття з другого абзацу можна опустити, оскільки ця перевірка нічого не дає. Кількість ребер $%2n-1$%, необхідне для зв'язності графа, дуже далеко від того, щоб бути достатнім.
Міркування щодо індукції тут якщо й можливе, то в якомусь складному варіанті. У нас граф має парну кількість вершин. Для застосування індукційного припущенняприйде якось вдало відкинути дві вершини, але при цьому ступеня можуть сильно зменшитися.
Далі, нам не дано за умови, що вихідний граф зв'язаний. Зрозуміло, це правильно, оскільки граф і після видалення ребер залишиться зв'язковим, але спиратися такий факт ми можемо, оскільки він ще встановлено.
Те, що при видаленні $%n-1$% ребра кожна вершина з'єднана з рештою, вірно. Але цього мало встановлення зв'язності. Звідси випливає лише те, що після видалення ребер не виникає ізольованих вершин, але цього мало.
Міркування я можу запропонувати ось яке. Припустимо, що після видалення ребер граф виявився не зв'язковим. Тоді виникає принаймні два зв'язкових компоненти, і в тієї з них, у якій найменше вершин, їх не більше половини від загальної кількості, тобто не більше $%n$%. Позначимо через $%A$% безліч її вершин, і нехай $%B$% - безліч інших вершин.
Оскільки граф простий, а вершин $%A$% є $%k\le n$%, ступінь кожної вершини з $%A$% не перевищує $%k-1$% (мова про підграфу з безліччю вершин $%A $%, отриманому після видалення ребер). Але у вихідному графі ступінь кожної вершини дорівнював $%n$%. Це означає, що для кожної вершини з $%A$% ми видалили щонайменше $%n-k+1$% ребро. Неважко помітити, що для всіх вершин ці ребра будуть різними, тому що вони з'єднують вершини з $%A$% з вершинами з $%B$%. Це означає, що загальна кількість ребер, що видаляються, склала як мінімум $%k(n-k+1)$%, і за умовою воно строго менше $%n$%. Тоді має місце нерівність $%nk-k^2+k-n
Неважко помітити, що для всіх вершин ці ребра будуть різними, тому що вони з'єднують вершини A з вершинами B.
Я не зрозумів цього моменту. Тобто у нас виходить дводольний граф, де A і це різні частки?
Ні,вони не дводольні, тому що можуть бути ребра, що з'єднують вершини A між собою, а також B між собою. Але якщо на ці ребра не звертати уваги, ми дійсно отримаємо дводольний граф. Число ребер в ньому оцінюється, і воно виявляється досить великим, не меншим $%n$% за кількістю. Тому безліч А і В неможливо "розірвати", видаляючи менше n ребер. У цьому є основна ідея.
Безліч А у нас обов'язково виходить зв'язковим?
Так, це так за визначенням, тому що A є зв'язкова компонента. Але ця обставина взагалі не важлива: простежувати треба лише необхідну частину міркування.