Читать онлайн «Теория графов в занимательных задачах»

О. И. Мельников Теория графов в занимательных задачах URSS О. И. Мельников ТЕОРИЯ ГРАФОВ В ЗАНИМАТЕЛЬНЫХ ЗАДАЧАХ Рекомендовано Научно-методическим центром учебной книги и средств обучения Министерства образования Республики Беларусь в качестве учебно-методического пособия для общеобразовательных школ Издание третье, исправленное и дополненное URSS МОСКВА ББК 22. 174 22. 1760 Мельников Олег Исидорович Теория графов в занимательных задачах. Изд. 3-е, испр. и доп. — М. : Книжный дом «ЛИБРОКОМ», 2009. — 232 с. В настоящей книге в занимательной форме изложены основы теории графов. Изучение этой дисциплины на факультативах в средней школе будет способствовать развитию математического мышления учащихся, умений моделирования и облегчит усвоение школьниками вычислительной техники. Книга предназначена для школьников и учителей; задачи из нее могут быть использованы при подготовке к математическим олимпиадам различных уровней. Первое издание книги, вышедшее в 2001 году, входит в различные рекомендательные списки и виртуальные библиотеки не только для школьников и учителей, но и для студентов. 1-е издание выходило под заглавием «Занимательные задачи по теории графов» Издательство «Книжный дом "ЛИБРОКОМ"». 117312, г. Москва, пр-т Шестидесятилетия Октября, д. 9. Формат 60x90/16. Печ. л. 14,5. Зак. № 1813. Отпечатано в ООО «ЛЕНАНД». 117312, г. Москва, пр-т Шестидесятилетия Октября, д. 11А, стр. 11. ISBN 978-5-397-00033-8 © Книжный дом «ЛИБРОКОМ», 2008 5027 ID 55804 1 н пин 785397 000338" Все права защищены. Никакая часть настоящей книги не может быть воспроизведена или передана в какой бы то ни было форме и какими бы то ни было средствами, будь то электронные или механические, включая фотокопирование и запись на магнитный носитель, а также размещение в Интернете, если на то нет письменного разрешения владельца. Решения задач 8 Использованная литература 226 Приложение 227 Посвящается Регине Иосифовне Тышкевич Введение Современная математика уже не такая, какой она была в начале XX века. В ней появилось большое количество новых дисциплин, широко применяющихся на практике. К таким дисциплинам, например, относятся дисциплины, объединенные под общим названием «Дискретная математика». Математическая энциклопедия говорит о дискретной математике как о ряде математических теорий, не связанных непосредственно с концепцией предельного перехода и непрерывности. Дискретная математика является в настоящее время очень интенсивно развивающимся разделом математики. Это связано с повсеместным распространением кибернетических систем, языком описания которых она является. Кроме того, дискретная математика является теоретической базой информатики, которая все глубже и глубже проникает не только в науку и технику, но и в повседневную жизнь.