Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



Рівнобедрені графи

Скачати 101.13 Kb.

Рівнобедрені графи




Скачати 101.13 Kb.
Дата конвертації31.03.2017
Розмір101.13 Kb.
ТипЗадача

Рівнобедрені графи




Олександр Рибак


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


Почнемо з простої задачі, яка була на Заочній Всеукраїнській олімпіаді 2005 року.

Задача 1. Чи можна посадити шість яблунь таким чином, щоб будь-які три з них знаходилися у вершинах рівнобедреного трикутника?
Ре́бра (лат. Costae) - парні кістки осьового скелету хребетних тварин (за винятком безщелепних), що з'єднуються з хребтом. У риб ребра дають опору міосептам тулубної мускулатури; появу ребер у філогенезі позв'язують з посиленням локомоції в щелепних.
Доведення у математиці - процедура, за допомогою якої встановлюють істинність гіпотези чи будь-якого твердження.
Ко́лір (також ба́рва у контексті теми) - суб'єктивна характеристика сприйняття світлової хвилі, яка ґрунтується на здатності людського зору розрізняти електромагнітне випромінювання з довжиною хвиль в області видимого діапазону (видимий діапазон - довжини хвиль від 380 до 760 нм).
Трику́тник у евклідовій геометрії - три точки, що не лежать на одній прямій, і три відрізки, що їх сполучають. Трикутник з вершинами A, B, і C позначається ABC. Трикутник є многокутником і 2-симплексом.

Розв’язання залишаємо читачам. Можна розглянути більш загальне питання, відмовившись від геометричної теми.

Читання - один з найважливіших видів мовної діяльності, тісно пов'язаний як з вимовою, так і з розумінням мови. Також «читання» - це здатність сприймати, розуміти інформацію, яка записана (передана) тим або іншим способом або відтворена технічними пристроями.
Питання - форма думки, виражена в мові пропозицією, яку виголошують або пишуть, коли хочуть що-небудь запитати, тобто отримати інформацію, що цікавить. В українській мові, якщо питання виголошують, то використовують питальну інтонацію, а якщо пишуть, то в кінці ставлять знак питання і використовують питальні частки: чи, не… чи, що, як, чи що, то хіба, невже, що якщо, а, так, правда, чи не так, так, але ж, чи не так, вірно; питальні займенникові слова: хто, що, який, який, чий, який, скільки, як, де, куди, звідки, коли, чому, навіщо, наскільки. За допомогою цих засобів будь-яка непитальна пропозиція може стати питанням або перезапитом. Задаючи питання зазвичай чекаємо відповіді. Виняток становить лише риторичне питання, на яке відповідь не потрібна.
Геометрія Геоме́трія (від дав.-гр. γη - Земля і μετρέω - вимірюю; землеміряння) - розділ математики, наука про просторові форми, відносини і їхні узагальнення.
А саме, нехай є декілька яблунь, і між кожними двома пролягає стежка деякої довжини. Стежки можуть бути і кривими, тому вважаємо, що їх довжини не пов’язані жодними співвідношеннями. Можна розглядати навіть не довжини стежок, а їх кольори. Позначимо яблуні вершинами графа, а стежки – ребрами відповідних кольорів. Для цього графа виконується умова, що у будь-якому трикутнику, утвореному його ребрами, знайдеться два ребра однакового кольору. Графи з вказаною властивістю будемо називати рівнобедреними. Їх дослідженню і присвячена ця стаття.

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

Льонок звичайний (лат. Linaria vulgaris Mill.) - вид губоцвітих рослин родини Подорожникові (Plantaginaceae).
І́стина - одна з центральних категорій гносеології, правильне відображення об'єктивної дійсності у свідомості людини, її уявленнях, поняттях, судженнях, умовиводах, теоріях об'єктивної дійсності.


Твердження 1. Рівнобедрений граф, який містить більше однієї вершини, не може бути зв’язним більше, ніж за двома кольорами.

Доведення. Використаємо індукцію за кількістю вершин графа.
Інду́кція (англ. induction) - термін широкого призначення: явище, що виникає під зовнішнім впливом; у гуманітарних науках та стосовно людського мислення - метод пізнання, що ґрунтується на формально-логічному умовиводі, який дає можливість одержати загальний висновок на основі аналізу окремих фактів.


База індукції. Граф з двома вершинами є зв’язним тільки за одним кольором.

Перехід індукції. Нехай для графа з k (k≥2) вершинами твердження вірне. Припустимо, що існує рівнобедрений граф Gk 1 з k 1 вершиною, який є зв’язним принаймні за трьома кольорами, які ми позначимо через x, y і z. Розглянемо граф Gk, який отримується з Gk 1 вилученням деякої вершини W (та прилеглих до неї ребер). Він теж є рівнобедреним, тому за припущенням індукції цей граф не зв’язний принаймні за одним з трьох вищезгаданих кольорів. Нехай, наприклад, Gk не зв’язний за кольором z. Позначимо через A1, A2, ..., Am (m≥2) компоненти зв’язності, які виникнуть у Gk, якщо у ньому залишити лише ребра кольору z. Покажемо, що для будь-яких двох компонент Ai та Aj (ij) всі пари вершин, одна з яких належить Ai, а інша – Aj, з’єднані ребрами одного й того самого кольору. Нехай вершини K, L належать Ai, а вершини M, N – Aj. Через (V1V2) будемо позначати колір ребра, яке сполучає вершини V1 та V2. Потрібно довести, що (KM)=(LN).

Спочатку доведемо, що (KM)=(LM). Випадок K=L очевидний, тому нехай K≠L. Оскільки компонента Ai зв’язна за кольором z, в Ai знайдуться вершини K0=K, K1, ...

Компоне́нт (від лат. componens, родовий відмінок componentis - складаючий) - складова частина, елемент чого-небудь.
, Kp=L, для яких (K0K1)=(K1K2)=...=(Kp 1Kp)=z. Для будь-якого цілого i (0≤ip-1), за умовою рівнобедреності Gk, серед кольорів (KiKi 1), (KiM) та (Ki 1M) знайдуться два однакових. Але, оскільки MAi, кольори (KiM) та (Ki 1M) не можуть дорівнювати z. На відміну від них, (KiKi 1)=z. Отже, рівними можуть бути тільки кольори (KiM) та (Ki 1M). Застосовуючи рівність (KiM)=(Ki 1M) для i від 0 до p-1, отримуємо (KM)=(K0M)=(K1M)=...=(KpM)=(LM). Аналогічно доводиться (LM)=(LN).
Рівність перед законом - одна з фундаментальних конституційних вимог, важлива умова існування правової держави. Принцип рівності є логічним продовженням принципу справедливості. Зміст 1 Загальна характеристика 2 Генезис ідеї рівності 3 Формальна рівність 4 Фактична рівність 5 Див.
Анало́гія - (грец. αναλογια - «відповідність») - подібність, схожість у цілому відмінних предметів, явищ за певними властивостями, ознаками або відношеннями.
Отже, для довільних вершин K, L  Ai та M, N  Aj доведено (KM)=(LM)=(LN).

Згідно з доведеним, через [AiAj] (ij) можна позначити той єдиний колір, який мають ребра, що сполучають пари вершин, одна з яких належить Ai, а друга – Aj.

Оскільки ми припустили, що граф Gk 1 є зв’язним за кольорами x, y та z, то з вершини W до Gk має виходити хоча б по одному ребру кольорів x та y, а до кожної з компонент A1, A2, ..., Am – хоча б одне ребро кольору z. Нехай R, S – вершини, для яких (WR)=x та (WS)=y. Нехай RAr, SAs. Для будь-якої компоненти At, відмінної від Ar, буде виконуватися [ArAt]=x. Дійсно, нехай T – вершина у At, для якої (WT)=z – така вершина має існувати. За умовою рівнобедреності Gk 1, серед кольорів (WR), (WT), (RT) знайдуться два однакових. Помітимо, що (WR)=xz=(WT), тому (RT) дорівнює x або z. Але (RT)≠z, бо R та T лежать у різних компонентах Ar та At відповідно. Тому [ArAt]=(RT)=x. Аналогічно, для будь-якої компоненти At, відмінної від As: [AsAt]=y.

Нехай rs. Підставляючи t=s, маємо [ArAt]=[ArAs]=x, а для t=r отримуємо [AsAt]=[AsAr]=y. Але цього не може бути, бо [ArAs]=[AsAr]. Якщо ж r=s, то існує компонента At, відмінна від Ar=As. Тоді одночасно повинно бути [AsAt]=[ArAt]=x та [AsAt]=y, що неможливо.

Отже, Gk 1 не може бути зв’язним за трьома кольорами. □


Будемо казати, що граф є зв’язним за даним набором кольорів, якщо кожні дві його вершини можна з’єднати таким ланцюжком ребер, що колір кожного ребра є в наведеному наборі.

Твердження 2. Рівнобедрений граф, який є зв’язним за деяким набором кольорів, також є зв’язним за деяким одним кольором з цього набору.

Доведення. Нехай рівнобедрений граф G є зв’язним за набором кольорів (c1c2, ..., cn). Знову застосуємо індукцію. В даному випадку – за кількстю кольорів n.

База індукції. Випадок n=1 очевидний.

Перехід індукції. Нехай n≥2, і нехай твердження вірне для n 1 кольору. Припустимо, що G не зв’язний за кольором cn, інакше твердження вже доведене. Нехай A1, A2, ..., Am (m≥2) – компоненти зв’язності відносно кольору cn. Як ми показали у доведенні твердження 1, для кожної пари індексів i, j (ij) між компонентами Ai та Aj пролягають ребра тільки одного кольору, який ми позначали як [AiAj]. Побудуємо новий граф H з вершинами V1, V2, ..., Vm, де кожна вершина Vi відповідає компоненті Ai графа G. Для кожної пари i, j (1≤i<jm) між Vi та Vj проведемо ребро кольору [AiAj].

Очевидно, граф H є рівнобедреним та зв’язним за набором (c1c2, ..., cn), як і граф G. Колір cn не зустрічається у графі H, тому він зв’язний навіть за набором (c1c2, ..., cn 1). Тоді, за припущенням індукції, H зв’язний за деяким кольором ck. Покажемо, що G також є зв’язним за ck. Розглянемо вершини W1 та W2 графа G. Спочатку розглянемо випадок, коли вони лежать у різних компонентах Ai та Aj. У графі H цим компонентам відповідають вершини Vi та Vj, які з’єднані ланцюжком ребер кольору ck. Нехай (Vq(0)=Vi, Vq(1), ..., Vq(r)=Vj) – послідовність вершин у цьому ланцюжку.

Ланцю́жок або ланцю́г - ювелірний виріб, що складається з багатьох однакових елементів, ланок, які сполучені між собою гнучким з'єднанням.
Послідо́вність - функція визначена на множині натуральних чисел яка набуває значення на об'єктах довільної природи. f : N → X \,\rightarrow \,\!X} .
Замість кожного Vq(l) (0≤lr) візьмемо деяку вершину Xl з компоненти Aq(l), причому в якості X0 та Xr оберемо саме W1 та W2 відповідно. Вийде ланцюжок у графі G, який з’єднує W1 та W2 і ребра якого мають колір ck. Залишився випадок, коли W1 та W2 належать одній компоненті Ai. Розглянемо вершину Vi у графі H. З неї має виходити ребро кольору ck, адже H зв’язний за ck і містить більше однієї вершини. Нехай Vi з’єднана ребром згаданого кольору з деякою Vj. Нехай X – деяка вершина у відповідній компоненті Aj. Тоді (W1, X, W2) – потрібний ланцюжок.

Отже, G зв’язний за кольором ck. □

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

Інструмент Інструме́нт (лат. instrumentum - знаряддя) - технологічне оснащення (знаряддя або пристрій), які в процесі праці безпосередньо стикаються з предметом праці з метою зміни чи контролю його форми, стану, властивостей тощо.
Дослідження Дослі́дження, до́сліди - (широко розуміючи) пошук нових знань або систематичне розслідування з метою встановлення фактів; (вузько розуміючи) науковий метод (процес) вивчення чого-небудь.
Тепер можна довести теорему, з якої випливає їх повний опис.

Теорема про структуру рівнобедрених графів. Нехай рівнобедрений граф G має більше однієї вершини. Тоді вершини G можна розділити на підмножини A1, A2, ..., Am (m≥2) таким чином, що для кожної пари i, j (1≤i<jm) всі ребра між Ai та Aj мають один і той самий колір [AiAj]. При цьому для всіх можливих i, j (1≤i<jm) колір [AiAj] набуває не більше двох різних значень.

Доведення. Розглянемо всі кольори c1, c2, ..., cn, за якими G не зв’язний. З твердження 2 випливає, що G не зв’язний і за всім набором (c1, c2, ..., cn). Нехай A1, A2, ..., Am (m≥2) – компоненти зв’язності відносно цього набору кольорів. Перефарбуємо ребра кольорів c2, ..., cn у колір c1. Тоді A1, A2, ..., Am стануть компонентами зв’язності за c1. Граф залишиться рівнобедреним, оскільки пари ребер однакового кольору перетворяться на пари однакового кольору. У доведенні твердження 1, показано, що в такому випадку всі ребра між Ai та Aj мають один і той самий колір [AiAj].

Згідно з вибором кольорів c1, c2, ..., cn, за всіма іншими кольорами d1, ..., dp граф G є зв’язним. [AiAj] може набувати лише значення d1, ..., dp. А таких кольорів, за твердженням 1, не більше двох, що й треба було довести. □


Перейдемо до опису рівнобедрених графів.

Будемо називати граф двоколірним, якщо будь-яка пара його вершин з’єднана ребром, і кожне ребро пофарбоване в один з двох кольорів. У графі не обов’язково мають бути присутні рівно два кольори – важливо, щоб множина наявних кольорів містила не більше двох елементів. Будь-який рівнобедрений граф можна отримати таким чином. Розглянемо деякий двоколірний граф (вершини якого відповідають компонентам A1, A2, ..., Am, згаданим у доведенні теореми). Для нього декілька разів повторимо наступну операцію: оберемо деяку вершину V і замінимо її деяким двоколірним графом H, а кожну вершину WH з’єднаємо з усіма вершинами H ребрами того кольору, який був у ребра VW.

Опера́ція (лат. operatio - дія, вплив) - дії, заходи, що виконуються за певним планом і спрямовані на вирішення якогось завдання, досягнення якоїсь мети або належить до кола функцій даного підприємства, установи, відділу, окремого працівника, певного обладнання тощо.
Обернений факт очевидний – будь-який граф, побудований вказаним чином, є рівнобедреним.

Коротшим є рекурентне описання: будь-який рівнобедрений граф G (|G|≥2) отримується з деякого двоколірного графа H (|H|≥2) заміною кожної вершини H рівнобедреним графом.

Наостанок покажемо, як доведені твердження допомагають у розв’язанні деяких задач.


Задача 2 (відбори команди України на ММО, 2005 рік). Кожну сторону та діагональ опуклого многокутника пофарбовано в один з k кольорів. Для кожного кольору a та кожної пари різних вершин многокутника A і B або існує така вершина C, що відрізки AC і BC пофарбовано в колір a, або сам відрізок AB пофарбовано в колір a. Також відомо, що не існує трикутника з вершинами серед вершин даного многокутника, сторони якого пофарбовано в три різні кольори. Довести, що k≤2.
Журі відборів запропоновало спеціальний розв’язок, але для нас задача є простим наслідком твердження 1.
Сторона́ - слово, яке має різні значення: Сторона (частина) геометричної фігури; Одна з двох сторін грамплатівки, диску, монети; Сторона світу; Місцевість; Сторона договору, правовідносин; Держава у дипломатичних взаєминах.
Многоку́тник[К 1] (багатоку́тник, поліго́н) - геометрична фігура, замкнена ламана (сама, або разом із точками, що лежать усередині). Вершини цієї ламаної називають вершинами многокутника, а відрізки ламаної - сторонами многокутника.
Причи́нність, також причи́нно-наслідко́вий зв’язо́к, причи́новість, причи́ново-наслідко́вий зв’язо́к, кауза́льність - (неформально, нестрого розуміючи) зв’язок між подією А («причиною») й іншою подією Б («наслідком»), яка необхідно настає за першою чи витікає з неї.

Задача 3 (відбори команди України на ММО, 2007 рік). Є 25 людей, кожні двоє з яких спілкуються деякою мовою. Причому будь-які двоє людей спілкуються між собою тільки однією мовою, навіть якщо вони знають і інші спільні мови. Відомо, що серед будь-яких трьох людей знайдеться принаймні одна людина, яка спілкується з двома іншими з цих трьох однією й тією самою мовою. Доведіть, що знайдеться людина, яка спілкується однією й тією самою мовою з деякими 10 іншими людьми.
Люди́на (лат. Homo) - рід приматів родини гомінід. Включає вид людина розумна (Homo sapiens) і близкі до нього вимерлі види. Предками Homo вважаються австралопітеки.


Розв’язання. Побудуємо граф G, у якому людей позначимо вершинами, а мови – ребрами відповідних кольорів. Тоді G – рівнобедрений. Отже, за теоремою про структуру рівнобедрених графів, він складається з деяких компонент A1, A2, ..., Am (m≥2), і для кожної пари i, j (1≤i<jm) всі ребра між Ai та Aj мають один і той самий колір [AiAj]. При цьому для всіх i, j (1≤i<jm) граф G зв’язний за кольором [AiAj], а тому таких кольорів не більше двох.

Якщо m≥5, розглянемо найменшу компоненту Ak серед A1, A2, ..., Am. Нехай VAk. Тоді V з’єднана з вершинами всіх інших компонент лише ребрами кольорів d1 та d2. Очевидно, таких вершин не менше 20. Тому принаймні з 10 вершинами V з’єднана одним і тим самим кольором. Нехай тепер m≤4. Якщо G зв’язний лише за одним кольором, то будь-яка вершина найменшої компоненти Ak з’єднана цим кольором принаймні з 13 іншими вершинами. Якщо ж G зв’язний за двома кольорами d1 та d2, то m=4 і компоненти A1, A2, A3, A4 можна перенумерувати так, щоб було [A1A2]=[A2A3]=[A3A4]=d1. Тоді або |A1| |A3|≥13, або |A2| |A4|≥13. У першому випадку підходить вершина з A2, у другому – з A3.


Задача 4. У трьох країнах є декілька школярів, які товаришують між собою.
Школярі - село в Україні, у Жовківському районі Львівської області, орган місцевого самоврядування - Замочківська сільська рада. Населення становить 68 осіб (станом на 2001 рік). Село розташоване у центрі Жовківського району, за 8,7 кілометра від районного центру.
Краї́на - це територія з визначеними кордонами й населенням, що являє собою єдине ціле з погляду історії, культури, нації та в політико-географічному відношенні може бути незалежною або залежною. Країна не завжди є державою, наприклад Україна в 1900 р.
Будь-які два школяра з різних країн спілкуються між собою мовою однієї з тих країн, в яких вони живуть. Також відомо, що серед будь-яких школярів з трьох різних країн знайдеться той, хто спілкується з іншими двома мовою своєї країни. Довести, що знайдуться такі школяр x та країна M, відмінна від тої, в якій живе x, що x спілкується з усіма своїми товаришами з M мовою своєї країни.

Розв’язання. Вважаємо, що всередині країни школярі спілкуються мовою своєї країни. Розглянемо граф, у якому школярі позначені вершинами, а мови – кольорами ребер. Цей граф – рівнобедрений. Згідно з твердженням 1, такий граф не зв’язний за одним з трьох кольорів, що відповідає мові деякої країни M. Нехай x – школяр, який не є досяжним з країни M за допомогою ребер, що відповідають мові країни M. Пара (x, M) виявляється шуканою. □
Остання задача пропонується для самостійного розв’язання.

Задача 5 (Всеукраїнська олімпіада з математики, 2007 рік). Довести, що у рівнобедреному графі з n вершинами є ребра не більше, ніж n 1 різного кольору.


Скачати 101.13 Kb.