Введення. 
Ейлерові графи

Перша робота з теорії графів, що належить відомому швейцарському математику Л. Ейлера, з’явилася в 1736 г. Спочатку теорія графів здавалася досить незначним розділом математики, так як вона мала справу в основному з математичними розвагами й головоломками. Однак подальший розвиток математики і особливо її додатків дало сильний поштовх розвитку теорії графів. Вже в XIX столітті графи використовувалися при побудові схем.

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

У цій роботі ми докладніше розглянемо Ейлерови графи, основні відомості і теореми, пов’язані з цим поняттям. А також завдання, які вирішуються за допомогою ейлеровим графів.

теорія графа кенігсберзький ейлеровий.

Теоретична частина

Основні поняття теорії графів

Граф G — пара (V, X), де V кінцеве непорожнє безліч, що містить p вершин, а безліч Х містить q невпорядкованих пар різних вершин з V.

Кожну пару X = {u, v} вершин у Х називають ребром графа G і кажуть, що Х з'єднує u і v. Ми будемо писати X = uv і говорити, що u і v — суміжні вершини. Вершина u і ребро Х інцидентних, так само як v і Х. Якщо два різних ребра X і Y інцидентних однієї і тієї ж вершині, то вони називаються суміжними. Граф з р вершинами і q ребрами називається (p; q) — графом. Граф (1,0) — називається тривіальним. Якщо елементом множини V може бути пара однакових елементів u, то такий елемент безлічі V називається петлею. [3].

Типи графів:

• · Мультиграф, в ньому не допускаються петлі, але пари вершин можуть з'єднуватися більш ніж одним ребром, ці ребра називаються кратними.
• · Псевдограф, в ньому допускаються петлі і кратні ребра (рис.2).

Рис. 1.

Рис. 2.

Орієнтований граф, або орграф, складається з кінцевого непорожньої безлічі V вершин і заданого набору Х впорядкованих пар різних вершин. Елементи з Х називаються орієнтованими ребрами, або дугами. Ні петель і кратних дуг (рис. 3).

Рис. 3.

Рис. 4.

• · Спрямований граф — це орграф, що не має симетричних пар орієнтованих ребер (рис. 4).
• · Помічені графи (або перенумеровані), якщо його вершини відрізняються одна від одної будь-якими позначками. Як позначок зазвичай використовуються букви або цілі числа. [6]

Ступенем вершини v _i у графі G називається число ребер, інцидентних v _i, Позначається d _i. [6] Для орграфа вводяться поняття ступеня входу і виходу. Ступенем виходу вершини v називається кількість ребер, для яких v є початковою вершиною, позначається outdeg (v). Ступенем входу вершини v називається кількість ребер, для яких v є кінцевою вершиною, позначається indeg (v). Якщо indeg (v) = 0, то вершина v називається джерелом. Якщо outdeg (v) = 0, то вершина v називається стоком. [1].