Стаття Про графи з кольоровими ребрами
Якщо на площині розташовані кілька точок і лінії, кожна з яких з'єднує пару наших точок, то кажуть, що заданий граф. Крапки називаються вершинами графа, а лінії – його ребрами. Ребра графа можуть бути забарвлені у кілька кольорів, тоді його називають графом із кольоровими ребрами. На малюнку 1а зображено граф із п'ятьма вершинами та ребрами двох кольорів. Той самий граф можна зобразити й іншими несхожими малюнками, наприклад, 1б і 1в.
Справді, граф із кольоровими ребрами можна ставити таблицею з n рядками і n стовпцями, де n - число вершин. Для цього потрібно занумерувати вершини, і на перетині i-го рядка та j-го стовпця таблиці написати колір ребра, що з'єднує i-ю та j-ю вершини. Легко збагнути, що можна занумерувати вершини графів на рисунках 1а, б і так, що таблиці виявляться однаковими. Саме тому ми й кажемо, що це – той самий граф.
У цій статті розглядаються лише такі графи, у яких кожна пара вершин з'єднана руба. Такі графи називають повними. Однак, оскільки інших графів тут не розглядається, ми щоразу не писатимемо слово "повний".
Застосування графів з кольоровими ребрами полегшує вирішення деяких завдань і робить їх наочнішими.
Перейдемо тепер до вирішення завдань.
Завдання 1. Шість школярів беруть участь у шаховому турнірі, який проводиться в одне коло. Доведіть, що завжди серед них знайдуться три учасники турніру, які провели вже всі зустрічі між собою, або ще не зіграли один з одним жодної партії.
Рішення. Будь-які два учасники турніру перебувають між собою неодмінно в одному із двох відносин: вони або вже зіграли між собою партію, або ще не зіграли. Кожному учаснику поставимо у відповідність вершинуграфа. З'єднаємо вершини попарно ребрами двох кольорів. Нехай ребро червоного кольору означає, що двоє зіграли між собою, а синього - що не зіграли. Ми отримали граф з шістьма вершинами та ребрами двох кольорів. Тепер для вирішення завдання достатньо довести, що в такому графі обов'язково знайдеться трикутник з одноколірними сторонами.
Зауважимо, що з довільної вершини нашого графа до п'яти інших неодмінно вийдуть щонайменше три ребра одного кольору (доведіть це). Нехай, наприклад, з вершини A виходять три ребра червоного кольору (рис.2) Якого кольору ребра можуть з'єднувати вершини B, C та D)? Якщо хоча б одне з них виявиться червоним, як на малюнку 3, то вийде трикутник із червоними сторонами. Якщо всі ці ребра сині, як у малюнку 4, всі вони утворюють трикутник з синіми сторонами.
Завдання повністю вирішено. Крім того, при її вирішенні доведено дві властивості.
Властивість 1. З будь-якої вершини графа з шістьма або більше вершинами та ребрами двох кольорів виходить щонайменше три ребра одного кольору.
Властивість 2. У будь-якому графі з шістьма або більше вершинами та ребрами двох кольорів знайдеться щонайменше один трикутник із одноколірними сторонами.
Завдання 2.На географічній карті обрано п'ять міст. Відомо, що з будь-яких трьох з них знайдуться два, з'єднані авіалініями, і два - не з'єднані. Доведіть, що тоді:
1. Кожне місто з'єднане авіалініями з двома і тільки з двома іншими містами.
2. Вилетівши з будь-якого міста, можна облетіти п'ять інших міст, побувавши в кожному по одному разу, і повернутися назад.
Рішення. Кожні два міста перебувають у одному з двох відносин - вони або з'єднані між собою авіалініями, або не з'єднані. Нехай вершини графа відповідають містам,червоне ребро – наявності авіалінії, синє – відсутності.
За умовою серед трьох ребер, що з'єднують будь-які три вершини, одне ребро - червоне, друге - синє, а це означає, що в графі немає жодного трикутника з одноколірними сторонами. Залишається показати, що у графі з п'ятьма вершинами та ребрами двох кольорів кожна вершина належить двом червоним і двом синім ребрам, причому, червоні ребра утворюють замкнуту лінію, що проходить через кожну вершину лише один раз, або інакше, що в такому графі знайдеться , всі боки якого – червоні, а всі діагоналі – сині.
Зрозуміло, що з кожної вершини графа виходять два червоні ребра і два сині, оскільки інакше утворився б трикутник з одноколірними сторонами. Отже, кожне місто з'єднане авіалініями з двома і лише з двома містами.
Тепер виберемо одну з вершин, наприклад A, а червоними будуть, скажімо, ребра АВ та АС (рис. 5). Ребро СВ може бути червоним, отже, червоним є одне з ребер або CD, або CE. Нехай червоне – CD. Якщо тепер з'єднати червоним ребром вершини B і D, то вершина E повинна бути з'єднана червоними ребрами з вершинами, які вже належать двом червоним ребрам. За умовою це неможливо. Залишається з'єднати червоними ребрами вершини D і E, B і E. Інші ребра мають бути синіми (рис. 1а).
Разом із розв'язанням задачі отримано ще одну властивість графа.
Властивість 3. Якщо у графі з п'ятьма вершинами та ребрами двох кольорів немає трикутника з одноколірними сторонами, то траф можна зобразити у вигляді "п'ятикутника" з червоними сторонами та синіми діагоналями.
Встановлено властивість графа, що є узагальненням властивості 2.
Властивість 4. У будь-якому графі з шістьма або більше вершинами та ребрами двох кольорів завжди знайдуться дватрикутник з одноколірними сторонами. Ці два трикутники можуть мати загальну вершину чи навіть загальне ребро.
Якщо два трикутники мають загальну вершину або загальне ребро, їх називають зчепленими.
Завдання 4.Назвемо групу людей "однорідної", якщо будь-які дві людини з цієї групи знайомі, або, навпаки, не знайомі. Доведіть, що серед восьми випадково зустрілися людей завжди знайдуться дві однорідні групи, що складаються з трьох осіб кожна, причому ніхто з першої групи не входить до другої.
Інакше кажучи, потрібно довести, що у графі з вісьмома вершинами і ребрами двох кольорів завжди знайдуться два не зчеплені трикутники з одноколірними сторонами.
Рішення. Розглянемо у графі одне із трикутників, наприклад KLM, з одноколірними сторонами. Якщо інші п'ять вершин і ребра, що з'єднують їх попарно, містять трикутник з одноколірними сторонами, він і буде другим шуканим трикутником. Якщо інші п'ять вершин A, B, C, D, E не містять трикутника з одноколірними сторонами, вони утворюють п'ятикутник з червоними сторонами і синіми діагоналями (властивість 3). На малюнку 7 зображені не всі ребра графа, а лише трикутник KLM з червоними сторонами та п'ятикутник ABCDE з червоними сторонами та синіми діагоналями. Покажемо, якщо якась вершина трикутника KLM з'єднана синіми ребрами з двома вершинами п'ятикутника, взятими через одну, наприклад, K з A і C (рис. 8), то знайдеться ще один трикутник з одноколірними сторонами, не зчеплений з трикутником АСК. Справді подивимося на п'ятикутник BDELM. Зрозуміло, що неможливо пофарбувати ребра BL і ВМ так, щоб він перетворився на п'ятикутник із червоними сторонами та синіми діагоналями. Тому він обов'язково містить одноколірний трикутник, не зчеплений зтрикутником АСК (рис. 9).
Залишається розглянути випадок, коли кожна вершина трикутника KLM з'єднана червоними ребрами щонайменше з трьома послідовними п'ятикутниками ABCDE. Нехай, наприклад, вершина K з'єднана червоними ребрами з вершинами A, B і C. Тоді вершини L і M з'єднані червоними ребрами з A, B і C. В іншому випадку знайдуться два незчеплені трикутники з вершинами K, L або M і основами - сторонами п'ятикутник ABCDE. Але тоді (див. рис. 10) ми знаходимо два трикутники CLM та АВК з червоними сторонами. Таким чином, у всіх випадках знайдуться два незчеплені трикутники з одноколірними сторонами.
Вирішимо тепер завдання, запропоноване на Шостій міжнародній математичній олімпіаді.
Завдання 5.Кожен із 17 учених листується з рештою. У їхньому листуванні йдеться про три теми. Кожна пара вчених листується один з одним лише з однієї теми. Доведіть, що не менше трьох вчених листуються один з одним по одній і тій же темі.
Рішення. Умовам завдання відповідає граф із сімнадцятьма вершинами та ребрами трьох кольорів. З кожної його вершини виходять 16 ребер, причому завжди не менше шести одного кольору. (Довести це неважко.) Якщо протилежні кінці хоча б двох з них з'єднані ребром того ж кольору, утворюється трикутник з одноколірними сторонами. Якщо ні, то 6 вершин будуть попарно з'єднані ребрами не більше ніж двох кольорів, а тоді, як ми вже знаємо (див. задачу 1), в цьому графі з шістьма вершинами знайдеться трикутник з одноколірними сторонами.
На закінчення наведемо кілька завдань самостійного рішення.
1. На одному із фестивалів зустрілися 6 делегатів. Виявилося, що з будь-яких трьох щонайменше двоє можуть порозумітися один з одним. Доведіть, щознайдуться три делегати, які можуть порозумітися один з одним,
2. У тривимірному просторі 9 точок розміщено так, що ніякі три не лежать на одній прямій. Кожна точка з'єднана відрізками прямих точно з чотирма іншими. Доведіть, що завжди знайдеться хоча б один трикутник із вершинами у цих точках.
3. У роботі міжнародного симпозіуму лінгвістів беруть участь n людина. З будь-яких чотирьох хоча б один може порозумітися з кожним із трьох учасників, що залишилися, хоча б однією мовою. Доведіть, що знайдеться учасник симпозіуму, який може порозумітися з кожним з інших учасників.
4. У місті n мешканців. Будь-які двоє з них або дружать, або ворогують, причому серед будь-яких трьох мешканців дружать або всі троє, або тільки двоє. Доведіть, що якщо не всі жителі цього міста – друзі, то знайдеться городянин, у якого більше ворогів, ніж друзів.
5. У місті n мешканців. Будь-які двоє з них або дружать, або ворогують. Щодня не більше одного з них може почати нове життя: посваритися з усіма друзями та подружитися з усіма ворогами. Відомо, що будь-які три мешканці можуть потоваришувати. Довести, що всі мешканці можуть потоваришувати.