Графы в обучении математике
Дипломная работа - Педагогика
Другие дипломы по предмету Педагогика
? , {V1, V6}, {V2, V3}, {V6, V6}}}.
Ребра {V1, V6}, {V2, V3} неориентированы. Для любого неориентированного ребра полагают, что {Vi, Vj} = {Vj, Vi} также, как и в случае неупорядоченных множеств. Ребро {Vi, Vi} называется петлей. На рис.1 имеем петлю {V6, V6}. Петли обычно ориентированы. На рис.1 приведен смешанный граф, т.е. содержащий как ориентированные, так и неориентированные ребра и петлю.
Вершина, не инцидентная ни одному ребру, называется изолированной. Вершина, инцидентная ровно одному ребру, и само это ребро называются концевыми, или висячими. Ребро с совпадающими концами называется петлей. Две вершины инцидентные одному и тому же ребру называются соседними (или смежными). Два ребра, инцидентные одной и той же вершине называются смежными. Ребра, которым поставлена в соответствии одна и та же пара вершин, называются кратными, или параллельными.
Граф, у которого вершины изолированы, называется нуль-графом. Множество ребер такого графа пусто.
Антиподом нуль-графа является полный граф. Ребрами полного графа являются все возможные пары его вершин.
Граф называется плоским, если он может быть изображен на плоскости так, что все пересечения ребер есть его вершины.
Если граф G представлен конечным множеством ребер, то он называется конечным, независимо от числа вершин. В противном случае граф называется бесконечным.
Граф Н называется частью графа G или частичным графом Н С G, если множество его вершин V (Н) содержится в множестве вершин V (G) графа G и все ребра Н являются ребрами G. Частным, но важным типом частичных графов являются подграфы.
Пусть А - подмножество множества вершин V графа G. Подграф G (A) графа G есть такая часть графа, множеством вершин которого является А, а ребрами - все ребра из G, оба конца которых лежат в А.
Для любой части Н графа определена дополнительная часть Н (дополнение), состоящая из всех тех ребер, которые не принадлежат Н, и всех инцидентных им вершин.
Неориентированный граф называется простым, если он не имеет петель и любая пара вершин соединена не более чем одним ребром.
Дополнением простого графа G называется граф , имеющий те же вершины, а его ребра являются дополнением G до полного графа.
Граф называется помеченным (или перенумерованным), если его вершины отличаются друг от друга какими-либо пометками.
2. Маршруты, циклы в графах
Пусть G - конечный граф. Маршрутом S в G называется последовательность ребер, S = (U1, U2, тАжUn), * в которой любые соседние два ребра Ui-1, Ui, (i=2, n) имеют общую вершину.
На графах допускаются маршруты, в которых не принимаются во внимание направления ребер. Такие маршруты называются неориентированными.
Пусть на графе определен маршрут (*). Та вершина ребра U1, которая не является общей с вершиной ребра U2, называется начальной вершиной маршрута S.
Аналогично вводится понятие конечной вершины маршрута: та вершина ребра Un, которая не является общей с вершиной Un-1, называется конечной вершиной маршрута S. Остальные вершины маршрута S называются внутренними.
Нуль-маршрутом называется маршрут, не содержащий ребер.
Вершина Ui называется достижимый из вершины Ui, если существует маршрут из Ui в Uj. Для определенности считают, что любая вершина Ui достижима из себя нуль-маршрутом независимо от наличия петель.
Неориентированный граф называется связным, если все его вершины попарно достижимы.
Неориентированный граф называется соотнесенным, если он получен из ориентированного либо смешанного графа заменой всех дуг на ориентированные ребра.
Маршрут называется циклом, если начальная и конечная вершины цепи равны. Другое определение цикла - замкнутая цепь, которое понимается в первоначальном определении. Цикл называется простым, если все его вершины различны.
Цепь называется циклом, если начальная и конечная вершины цепи равны. Другое определение цикла - замкнутая цепь, которое понимается в первоначальном определении. Цикл называется простым, если все его вершины различны.
Началом (концом) цикла можно считать любую из его вершин.
На ориентированном графе аналогично понятию цепи вводится понятие пути, а аналогично понятию цикла - понятие контура.
Путь - это ориентированная цепь. Контур - это замкнутый путь. Рассмотрим примеры различных маршрутов на графе G.
Маршрут (U4, U1, U2) является простой цепью.
Маршрут (U4, U1, U2, U3, U7, U1) цепью не является. поскольку ребро U1 встречается в нем дважды. Маршрут (U4, U3, U2, U1) представляет цепь, но не простую, поскольку вершина V3 встречается на ней дважды: как начало ребра U1 и как конец ребра U3. Такая цепь содержит в себе цикл. В данном случае в цепи (U4, U3, U2, U1) имеем цикл (U3, U2, U1). Этот цикл простой. Примером не простого цикла может служить маршрут (U1, U2. U3, U7, U6, U5).
Решим задачу 1.3. Может ли так случиться, что в одной компании из шести человек каждый знаком с двумя и только с двумя другими.
Решение. Участника этой компании изобразим вершиной графа, а отношение знакомства между двумя участниками ребром. Изобразим графы, которые могут соответствовать такой компании.
Итак, ситуация, рассмотренная в задаче, вполне возможна. Но случай соответствует не одной, а двум компаниям, участники одной из них не знакомы с участниками другой.
Про граф говорят, что он связный, так как из каждой вершины по ребрам можно попасть в любую другую. Делаем вывод, что в этом случае каждый через своих знакомых может познакомиться со всеми остальными.
Во втором случае получились два простых цикла, не