Лемма 2
Доведення. Вершини графа, що складається з ребер та вершин фіксованого багатогранника мають однаковий ступінь. Позначимо цей ступінь через x. Нехай y – кількість сторін межі цього багатогранника. Отримуємо систему рівнянь
.
Оскільки x,y 3, а у разі x,y 4 має місце нерівність , то можливі такі випадки: x=3 чи y=3.
Розглянемо випадок x=3:
.
x=3, y=3,;
x=3, y=4,;
x=3, y=5, .
Аналогічно x=4 x=5 при y=3.
§4.7. Вправи Властивості графів
Усі графи передбачаються простими. Графи називаються ізоморфними, якщо існує бієкція f між множинами вершин, така що ребро – ребро.
Довести, що граф має парне число вершин з непарними ступенями.
Під час зустрічі студентів відбулося 15 рукостискань, троє людей зробили по 4 рукостискання, а інші – по 3. Скільки було студентів.
Чи може існувати група з 23 осіб, кожна з яких знайома з п'ятьма іншими?
У змаганнях з шахів за круговою системою беруть участь 5 осіб. Усі, крім Іванова та Петрова, зіграли різну кількість партій. Скільки партій зіграли Іванов та Петров?
Чи можна намалювати без отвору олівця граф K6, у якого видалено одне ребро.
Знайти число попарно неізоморфних графів, які мають 2 вершини мають ступінь 2, 2 вершини мають ступінь 3, і 2 вершини мають ступінь 4. Інші вершини мають ступінь 0.
Знайти число попарно неізоморфних графів, які мають 3 вершини мають ступінь 2, 3 вершини мають ступінь 3, і 3 вершини мають ступінь 4. Інші вершини мають ступінь 0.
Довести, що у простому графі, що має не менше двох вершин, завжди знайдуться дві вершини однакового ступеня.
Які графи з наведених нижче ізоморфні:
Які графиз наступних нижче ізоморфні:
Знайти число всіх попарно неізоморфних графів, що мають 4 вершини. Намалювати ці графи.
Відповідь: (див. рис.4.8) існує 11 неізоморфних графів
Мал. 4.8. Графи, що мають 4 вершини
Найкоротший шлях, що з'єднує вершини u і v у графі, називається геодезичним шляхом між вершинами. Його довжина позначається d(u,v). Діаметром D() графа називається довжина найдовшого геодезичного шляху цьому графі, тобто. D()=max. Знайти діаметри графів
Матриця суміжності складається з коефіцієнтів aij=1 вершини i та j суміжні.
(1) Побудувати матриці суміжності для графів K3 та K4;
(2) Довести, що сума коефіцієнтів i-го рядка матриці суміжності дорівнює ступеню i-го вершини;
(3) Побудувати матрицю суміжності графа, що складається з вершин та ребер куба.
(4) За допомогою матриці суміжності збудує матрицю, коефіцієнтами якої є кількості шляхів довжини 2 з вершини i у вершину j.
(5) Як пов'язані слід матриці A 3 з числом трикутників у графі?
Цикли 1, z2, , zn>
Скільки компонент зв'язності має ліс, що містить 76 вершин та 53 ребра?
Довести, що серед 6 людей знайдеться трійка знайомих чи трійка незнайомих людей.
У компанії, що складається з п'яти студентів, серед будь-яких трьох знайдуться двоє знайомих і двоє незнайомих. Довести, що компанію можна розсадити за круглим столом таким чином, що будь-які два сусіди будуть знайомі.
Калькулятор
Сервіс безкоштовної оцінки вартості роботи
- Заповніть заявку. Фахівці розрахують вартість вашої роботи
- Розрахунок вартості прийде на пошту та по СМС
Номер вашої заявки
Зараз на пошту прийде автоматичний лист-підтвердження з інформацією про заявку.