Читать онлайн «Графы и их применение»

Л. Ю. БЕРЕЗИНА ГРАФЫ И ИХ ПРИМЕНЕНИЕ Л. Ю. БЕРЕЗИНА ГРАФЫ И ИХ ПРИМЕНЕНИЕ ПОСОБИЕ ДЛЯ УЧИТЕЛЕЙ МОСКВА «ПРОСВЕЩЕНИЕ» 1979 742С2 Б 48 Березина Л. Ю. Б48 Графы и их применение: Пособие для учителей. — М. : Просвещение, 1979. — 143 с. с ил. Книга знакомит читателя с основами теории графов и ее приложениями. Доступность изложения, сочетание вопросов теории с системой упражнений и иллюстраций дают достаточно полное представление об основных идеях и методах теории графов. Материал данного пособия может быть использован учителем для внеклассной работы с целью развития у учащихся интереса к предмету. Издательство «Просвещение», 1979 г. ОТ АВТОРА Если вы любите решать задачи на смекалку, логические, олим- пиадного типа или головоломки, то, наверное, не раз составляли таблицы, изображали объекты точками, соединяли их отрезками или стрелками, подмечали закономерности у полученных ри- суиков, выполняли над точками и отрезками операции, не похожие на арифметические, алгебраические или на преобразования в геометрии, то есть вам приходилось строить математический аппарат специально для решения задачи. А это означает, что вы заново открывали для себя начала теории графов. Исторически сложилось так, что теория графов зародилась именно в ходе решения головоломок двести с лишним лет назад. Очень долго она находилась в стороне от главных направлений исследований ученых, была в царстве математики на положении Золушки, чьи дарования раскрылись в полной мере лишь тогда, когда она оказалась в центре общего внимания. Толчок к развитию теория графов получила на рубеже XIX и XX столетий, когда резко возросло число работ в области топологии и комбинаторики, с которыми ее связывают самые тесные узы родства. Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кёнига в ЗО-е годы XX столетия. В последнее время графы и связанные с ними методы исследований органически пронизывают на разных уровнях едва ли не всю современную математику. Графы эффективно используются в теории планирования и- управления, теории расписаний, социологии, математической лингвистике, экономике, биологии, медицине. Широкое применение находят графы в таких областях прикладной математики, как программирование, теория конечных автоматов, электроника, в решении вероятностных и комбинаторных задач. Теория графов быстро развивается, находит все новые приложения и ждет молодых исследователей. 3 Конечно, в небольшой книге невозможно рассказать о всех направлениях развития теории графов и разработанных приложениях. Главная цель автора в другом — помочь учителю, а значит и школьникам, овладеть основными понятиями теории графов, новыми для школы методами решения задач, в популярной форме познакомить с некоторыми ее приложениями. Материал книги организован так, что знакомство с графами происходит в процессе решения самых разнообразных задач, в формулировках условий которых не упоминаются графы. Для решения их требуется «увидеть» возможность перевести условие на язык графов, решить задачу «внутри теории графов», интерпретировать полученное решение в исходных терминах.