Дискретная математика

120 Нужно выяснить, существует ли маршрут прогулки, проходящий через каждый мост один и только один раз и такой, что позволял бы, выйдя из произвопьной точки города, вновь вернуться в эту же точку. Эйлер доказал, что эта задача не разрешима. Но Эйлер не стал бы Эйлером в том смысле, как мы его воспринимаем, если бы он не обобщил принципы решения этой задачи и не создал основы теории подобных задач - теории графов. К теории графов сводятся задачи анализа электрических цепей, задачи перечисления изомеров предельных углеводородов некоторых веществ и ряд других задач. § 1. Основные типы графов Графом называется совокупность, состоящая из конечного множества F точек, называемых вершинами, и множества неупорядоченных пар различных вершин из К называемых ребрами. Множество вершин графа" можно, например, положить равным: V=(v /,v2,..., v „}. Множество ребер графа обозначим через X, а ребра через или через х,;,- (ij=\,2,...,n) или через (к~],2,...,т). Граф G с множеством вершин К и с множеством рёбер X записывается как G(V,X) или G, О ={У.Х). Вершину фафа изображают на рисунке (диаграмме фафа) точкой, а ребро (vi,vj) графа изображают линией, соединяющей вершины v, и v,-. Пример. Пусть Vj, v;, v> V4 - вершины графа, а (vj,v^, ('vj^v^J, (vs.vjt), - рёбра, тогда диаграмма этого графа представлена на рис. 5.2. а). На рис. 5.2 б) приведены всевозможные графы с треш вершинами, причем их вершины не помечены никакими символами и поэтому вершины не отличаются одна от 'другой какими-либо пометками. V/ V4 а) . б) . Рис. 5.2 Граф называется помеченным, если его вершины отличаются одна от другой какими-либо пометками, например у,, v^, ..., v „ , и непомеченным, если вершины графа не различаются (не отмечены). Каждая заданная неупорядоченная пара вершин х = (v,,v^ является ребром графа G. Считают, что х соединяет вершины V; и Vj. Мы будем писать и считать, что v; и V; - смежные вершины-, вершины v, и v,