стинками кольору 1) одно, коефіцієнту при в:
.
Загальне число різних орбіт (або намист) дорівнює
Висновок
Зараз майже в будь-якій галузі науки і техніки зустрічається застосування графів. У фізиці - при побудові електричних схем, в хімії та біології-при вивченні молекул і їх ланцюжків, в географії - при складанні карт, в історії - при складанні родоводу, в геометрії - у кресленнях багатокутників, багатогранників, просторових фігур, в економіці - при вирішенні завдань про вибір оптимального шляху для потоків вантажного транспорту (схем авіаліній, метро, ??залізниць).
граф є блок-схеми програм для ЕОМ, мережеві графіки будівництва. За допомогою графів вирішується завдання про призначення на посади.
Вивчаючи теорію перерахування графів доводиться вирішувати проблеми изоморфизмов для багатьох класів графів. Теорема перерахування Пойа, коли вона вперше стала широко цінуватися на початку 1960-х, служила основним інструментом для вирішення проблем изоморфизмов.
У цій роботі я вивчила опис цього інструменту. Для усвідомлення проблеми я розглянула перерахування помічених графів, це найбільш проста задача з теорії перерахування. Потім розглянула основні види графів, поняття теорії графів і теорії груп, поняття еквівалентності, лемму Бернсайда (William Burnside) і, нарешті, довела теорему Пойа.
Отже, практичний сенс теорії перерахування графів полягає в тому, щоб підрахувати число графів певного класу і оцінити трудомісткість задач, пов'язаних з перерахуванням виявленого безлічі об'єктів. Теорема Пойа дає нам механізм для проведення подібної оцінки.
Список використаних джерел
1.Burnside, William Theory of groups of finite order.- Cambridge University Press, 1897.
. Diestel R. Graph Theory, Electronic Edition.- NY: Springer-Verlag, 2005.
3.Балашова Н.А., Кукін Г.П. Комбінаторика. Омськ, 1992.
. Басакер Р., Сааті Т. Кінцеві графи та мережі М., Наука, 1974
. Бєлов В.В., Воробйов Є.М., Шаталов В.Є. Теорія графів. М.: ВШ, 1976.
. Березина Л.Ю. Графи та їх застосування: Посібник для вчителів.- М., 1979
. Берж Теорія графів та її застосування. М.: ІЛ, 1962.
. Емелічев В.А. Лекції з теорії графів.- М.: Наука, 1990.
. Зелянін Р.В. Деякі завдання перерахування графів - Сиктивкарський ГУ (сайт).
. Зиков А. А. Основи теорії графів.- М.: «Вузівська книга», 2004.
. Калужнін Л.А., СущанскійВ.І. Перетворення і перестановки - М.: Наука, 1985
12.Камерон П., ван Лінт Дж. Теорія графів. Теорія кодування і блок-схеми. М.: Наука, 1980.
. Комбінаторна прикладна математика / Под ред. Е.Беккенбаха.- М.: Світ, 1968.
. Комбінаторний аналіз. Завдання і вправи.- М.: Наука 1982
. Кофман А., Фор Р. Займемося дослідженням операцій. М.: Світ, 1966
. Крістофідес Н.Теорія графів. Алгоритмічний підхід. М.: Світ, 1978.
. Липський В. Комбінаторика для програмістів: Пер. з пол.- М.: Світ, 1988.
. Оре О. Графи та їх застосування. М., Мир, 1965.
. Оре О. Теорія графів.- М.: Наука, 1968.
. перечислительного завдання комбінаторного аналізу / Збірник переказів під редакцією Г.П. Гаврилова.- М.: Світ, 1979. <...
