Введення
граф теорема Пойа
Графи - це чудові математичні об'єкти, за допомогою, яких можна вирішувати математичні, економічні та логічні задачі. Також можна вирішувати різні головоломки і спрощувати умови задач з фізики, хімії, електроніці, автоматиці. Сама теорія графів є частиною як топології, так і комбінаторики.
Вирішення багатьох завдань перерахування графів зводиться до підрахунку числа класів еквівалентностей. Ефективний метод вирішення таких завдань базується на відомій теоремі Пойа.
Мета дослідження: вивчити основні властивості груп підстановок і метод вирішення комбінаторних задач за допомогою теореми Пойа.
Завдання дослідження:
. Вивчити такі основоположні поняття теорії графів і теорії груп, як граф, група підстановок і її циклової індекс.
. Розглянути визначення еквівалентності, що породжується групою підстановок, і довести лему Бернсайда про число класів такий еквівалентності.
. Розібрати визначення переліку конфігурації і довести теорему Пойа.
. Розглянути задачу про перерахування графів і метод її вирішення за допомогою теореми Пойа.
Об'єктом дослідження: теорія графів.
Предмет дослідження: групи підстановок і методи вирішення комбінаторних задач за допомогою теореми Пойа. Робота складається з двох розділів - теоретичної та практичної частини. У ходe роботи нами використовувалися слeдующиe мeтодов ісслeдованія: ізучeніe наукової, учeбной і мeтодічeской літeратури, Інтeрнeт-джерел, аналіз, обобщeніe і систематизація.
1. Теорема Пойа та перерахування графів
.1 Поняття теорії графів і теорії груп
У математичній теорії графів і інформатики граф - це сукупність непорожньої безлічі вершин і безлічі пар вершин (зв'язків між вершинами). Об'єкти представляються як вершини, або вузли графа, а зв'язки - як дуги, або ребра. Для різних областей застосування види графів можуть відрізнятися спрямованістю, обмеженнями на кількість зв'язків і додатковими даними про вершинах або ребрах [2].
Граф, або неорієнтовані граф - це впорядкована пара, для якої виконані наступні умови:
- це непорожнє безліч вершин або вузлів,
- це безліч пар (у разі неорієнтованого графа - невпорядкованих) вершин, званих ребрами.
(а значить і,, інакше воно було б мультімножество) зазвичай вважаються кінцевими множинами. Багато хороші результати, отримані для кінцевих графів, невірні (або будь-яким чином відрізняються) для нескінченних графів. Це відбувається тому, що ряд міркувань стає помилковим у разі нескінченних множин.
Вершини і ребра графа називаються також елементами графа, число вершин у графі - порядком, число ребер - розміром графа.
Вершини і називаються кінцевими вершинами (або просто кінцями) ребра. Ребро, в свою чергу, з'єднує ці вершини. Дві кінцеві вершини одного і того ж ребра називаються сусідніми. Два ребра називаються суміжними, якщо вони мають спільну кінцеву вершину. Два ребра називаються кратними, якщо множини їх кінцевих вершин збігаються. Ребро називається петлею, якщо його кінці збігаються, тобто. Ступенем вершини називають кількість інцидентних їй ребер (при цьому...
