ції розумової діяльності учнів.
1.3 Історія та основні поняття теорії графів
Початок теорії графів датують 1736, коли Л. Ейлер вирішив популярну в той час «задачу про кенігсберзькими мостах», що стала згодом однією з класичних задач теорії графів.
Леонард Ейлер (1707-1783) - математик, механік, фізик і астроном. Він автор понад 850 праць з механіки, теорії руху Місяця і планет, з географії, по теорії кораблебудування, теорії музики та інших наук.
Термін «граф» вперше був введений через 200 років (в 1936 р) Д. Кеніґом. Історію виникнення цієї теорії можна простежити по листуванню великого вченого. Ось переклад латинського тексту, який взятий з листа Ейлера до італійського математику і інженеру Маринони, відправленого з Петербурга 13 березня 1736 [17]:
рис. 3.1.1
Ніколи мені було запропоновано завдання про острів, розташованому в місті Кенігсберзі і оточеному річкою, через яку перекинуто сім мостів. Питається, чи може хто-небудь безперервно обійти їх, проходячи тільки одного разу через кожен міст. І тут же мені було повідомлено, що ніхто ще досі не міг це виконати, але ніхто і не довів, що це неможливо. Питання це, хоча й банальний, здався мені, проте, гідним уваги тим, що для його вирішення недостатні ні геометрія, ні алгебра, ні комбинаторное мистецтво. Після довгих роздумів було знайдено правило, засноване на цілком переконливому доказі, за допомогою якого можна у всіх завданнях такого роду відразу ж визначити, чи може бути здійснений такий обхід через яке завгодно число і як завгодно розташованих мостів або не може. КЄНІГСБЄРГСКІЄ ж мости розташовані так, що їх можна представити на наступному малюнку, на якому A позначає острів, а B, C і D - частині континенту, відокремлені один від одного рукавами річки. Сім мостів позначені буквами a, b, c, d, e, f, g :
З приводу виявленого їм способу вирішувати завдання подібного роду Ейлер писав що це рішення за своїм характером, мабуть, має мало відношення до математики, і мені незрозуміло, чому слід скоріше від математика очікувати (рис.1.3.1.) цього рішення, ніж від якого-небудь іншої людини, бо це рішення підкріплюється одним тільки міркуванням, і немає необхідності залучати для знаходження цього рішення будь-які закони, властиві математики. Отже, я не знаю, яким чином виходить, що питання, що мають зовсім мало відносини до математики, швидше дозволяється математиками, ніж іншими" .
Так чи можна обійти КЄНІГСБЄРГСКІЄ мости, проходячи тільки один раз через кожен з цих мостів (ріс.1.3.1)? Щоб знайти відповідь, продовжимо лист Ейлера до Маринони:
" Питання полягає в тому, щоб визначити, чи можна обійти всі ці сім мостів, проходячи через кожен тільки одного разу, чи не можна. Моє правило призводить до наступного вирішення цього питання. Перш за все, потрібно дивитися, скільки тобто ділянок, розділених водою, - таких, у яких немає іншого переходу з одного на інший, окрім як через міст. У даному прикладі таких ділянок чотирьох - A, B, C, D.
Далі потрібно розрізняти, чи є число мостів, що ведуть до цих окремих дільницях, парних або непарних. Так, в нашому випадку до ділянки A ведуть п'яти мостів, а до решти - по три мости, т. Е. Число мостів, що ведуть до окремих ділянок, непарній, а цього одного вже досить для вирішення завдання. Коли це визначено, застосовуємо наступне правило: якби число мостів, що ведуть до кожній окремій ділянці, було парним, то тоді обхід, про який йде мова, був би можливий, і в той же час можна було б почати цей обхід з будь-якої ділянки. Якщо ж з цих чисел дві були б непарні, бо тільки одне бути непарним не може, то й тоді міг би відбутися перехід, як це запропоновано, але тільки початок обходу неодмінно має бути взято від одного з тих двох ділянок, до яких веде непарне число мостів. Якщо б, нарешті, було більше двох ділянок, до яких веде непарне число мостів, то тоді такий рух взагалі неможливо ... якщо можна було привести тут інші, більш серйозні завдання, цей метод міг би принести ще більшу користь і їм не слід було б нехтувати" .
Слово «граф» в математиці означає картинку, де намальовано кілька точок, деякі з яких з'єднані лініями. Перш за все, варто сказати про те, що графи, про які піде мова, до аристократів минулих часів ніякого відношення не мають. Наші «графи» мають коренем грецьке слово «графо», що означає «пишу». Той же корінь в словах «графік», «біографія». У математиці визначення графа дається так: графом називається кінцеве безліч точок, деякі з яких з'єднані лініями. Точки називаються вершинами графа, а що з'єднують лінії - ребрами.
Схема графа, що складається з «ізольованих» вершин, називається нульовим графом (ріс.1.3.2).
Графи, в яких не побудовані вс...
