Графы Реферат по математике ученика 8 г класса Коротаева Дмитрия Муниципальное образовательной учреждение - МОУ Гимназия №47 Екатеринбург, 2000 Введение
    Слово "граф" в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. Графами являются блок - схемы программ для ЭВМ, сетевые графики строительства, где вершины - события, означающие окончания работ на некотором участке, а ребра, связывающие эти вершины, - работы, которые возможно начать по совершении одного события и необходимо выполнить для совершения следующего.
    Теория графов является частью как топологии, так и комбинаторики. То, что это топологическая теория, следует из независимости свойств графа от расположения вершин и вида соединяющих их линий. А удобство формулировок комбинаторных задач в терминах графов привела к тому, что теория графов стала одним из мощнейших аппаратов комбинаторики. Понятие о графах
    Математические графы с дворянским титулом "граф" связывает общее происхождение от латинского слова "графио" - пишу. Типичными графами являются схемы авиалиний, которые часто вывешивается в аэропортах, схемы метро, а на географических картах - изображение железных дорог (рис. 1). Выбранные точки графа называются его вершинами, а соединяющие их линии - ребрами.
    
    Использует графы и дворянство. На рисунке 2 приведена часть генеалогического дерева знаменитого дворянского рода. Здесь его вершины - члены этого рода, а связывающие их отрезки - отношения родственности, ведущие от родителей к детям.
    Слово "дерево" в теории графов означает граф, в котором нет циклов, то есть в котором нельзя из некоторой вершины пройти по нескольким различным ребрам и вернуться в ту же вершину. Генеалогическое дерево будет деревом и в смысле теории графов, если в этом семействе не было браков между родственниками.
    Не трудно понять, что граф - дерево всегда можно изобразить так, чтобы его ребра не пересекались. Тем же свойством обладают графы, образованные вершинами и ребрами выпуклых многогранников. На рисунке 3 приведены графы, соответствующие пяти правильным многогранникам. В графе соответствующем тетраэдру, все четыре вершины попарно соединены ребрами.
    
    
    Рассмотрим граф с пятью вершинами, попарно соединенными друг с другом (рис. 4). Здесь ребра графа пересекаются. Невозможно его изобразить так, чтобы пересечений не было, как невозможно выполнить намерения трех человек, описанных Льюсом Кэрроллом.
    Они жили в трех домиках, неподалеку от них находились три колодца: один с водой, другой с маслом, а третий с повидлом, и ходили к ним по тропинкам, изображенным на рисунке 5. Однажды эти люди перессорились и решили провести тропинки от своих домов к колодцам так, чтобы эти тропинки не пересекались. На рисунке 6 изображена очередная попытка проложить такие тропы.
    
    Графы, изображенные на рисунках 4 и 5, как оказалось, играют решающую роль при определение для каждого графа - является ли он плоским, то есть может ли он быть изображен на плоскости без пересечения его ребер. Польский математик Г. Куратовский и академик Л. С. Понтрягин независимо доказали, что если граф не является плоским, то в нем "сидит" хотя бы один из графов, изображенных на рисунках 4 и 5, то есть "полный пятивершинник" или граф "домики - колодцы".
    Графами являются блок - схемы программ для ЭВМ, сетевые графики строительства, где вершины - события, означающие окончания работ на некотором участке, а ребра, связывающие эти вершины, - работы, которые возможно начать по совершении одного события и необходимо выполнить для совершения следующего. ............