Категория
Информатика
Тип
реферат
Страницы
3 стр.
Дата
22.06.2009
Формат файла
.rtf — Rich Text Format (Wordpad)
Архив
20638.zip — 13.53 kb
  • algoritmy-na-grafax_20638_1.rtf — 75.92 Kb
  • Readme_docus.me.txt — 125 Bytes
Оцените работу
Хорошо  или  Плохо


Текст работы

Aлгоритмы на графах
Alena Alena
Aлгоритмы на графах
Элементы теории графов.
Граф - совокупность точек и линий, в которой каждая линия соединяет две точки. Точки называются вершинами, или узлами, графа, линии - ребрами графа. Если ребро соединят две вершины,
то говорят, что оно им инцидентно; вершины, соединенные ребром называются смежными. Две вершины, соединенные ребром, могут совпадать; такое ребро называется петлей.
Число ребер, инцидентных вершине, называется степенью
вершины. Если два ребра инцидентны одной и той же паре вершин, они называются
кратными; граф, содержащий кратные ребра, называется мультиграфом.
Ребро, соединяющее две вершины, может иметь направление от одной вершины к другой; в этом случае оно называется направленным, или ориентированным, и изображается стрелкой. Граф, в котором
все ребра ориентированные, называется ориентированным графом (орграфом); ребра орграфа часто называют дугами. Дуги именуются кратными, если они не только имеют общие вершины, но и совпадают по направлению. Иногда нужно рассматривать не весь граф, а его часть (часть вершин и часть ребер). Часть вершин и все инцидентные им ребра называются подграфом; все вершины
и часть инцидентных им ребер называются суграфом. Циклом называется замкнутая цепь вершин. Деревом называется граф без циклов. Остовным деревом
называется связанный суграф графа, не имеющий циклов.
Граф однозначно задан, если заданы множество его вершин, множество ребер и указаны все инцидентности (т.е. указано, какие вершины какими ребрами соединены). Наиболее наглядно граф задается рисунком; однако не все детали рисунка
одинаково важны; в частности, несущественны геометрические свойства ребер (длинна, кривизна и т.д.) и взаимное



Ваше мнение



CAPTCHA