Автор работы: Пользователь скрыл имя, 12 Декабря 2011 в 22:55, доклад
Некоторые основные понятия. Граф - совокупность точек (вершин) и совокупность пар этих точек (не обязательно всех), соединенных линиями (рис. 1,а). Если на графе линии ориентированы (т.е. стрелками показано направление связи вершин), они называются дугами, или ветвями; если неориентированы, - ребрами. Соответственно, граф, содержащий только дуги, называется ориентированным, или орграфом; только ребра-неориентированным; дуги и ребра - смешанным. Граф, имеющий кратные ребра, называется мультиграфом; граф, содержащий только ребра, принадлежащие двум его непересекающимся подмножествам (частям), - двудольным; дуги (ребра) и (или) вершины, которым отвечают определенные веса или числовые значения каких-либо параметров, - взвешенным.