Основные понятия теории графов
Граф - система, которая интуитивно может быть рассмотрена как множество кружков и множество соединяющих их линий {геометрический способ задания графа - см. рисунок 1). Кружки называются вершинами графа, линии со стрелками - дугами, без стрелок -ребрами. Граф, в котором направление линий не выделяется (все линии являются ребрами), называется неориентированным; граф, в котором направление линий принципиально (линии являются дугами) называется ориентированным.
Теория графов может рассматриваться как раздел дискретной математики (точнее - теории множеств), и формальное определение графа таково: задано конечное множество X , состоящее из n элементов (X = {1, 2,..., n}), называемых вершинами графа, и подмножество V декартова произведения X хХ, то есть VcX 2 , называемое множеством дуг, тогда ориентированным графом G называется совокупность ( X , V ) (неориентированным графом называется совокупность множества X и множества неупорядоченных пар элементов, каждый из которых принадлежит множеству X ). Дугу между вершинами i и j , i , j еХ, будем обозначать ( i , j ). Число дуг графа будем обозначать m ( V = ( v 1, v 2,..., v m )).
https://drive.google.com/file/d/0B2BeihKRHPZcWmNmdVB6dElyTnc/view?usp=sharing
Граф - система, которая интуитивно может быть рассмотрена как множество кружков и множество соединяющих их линий {геометрический способ задания графа - см. рисунок 1). Кружки называются вершинами графа, линии со стрелками - дугами, без стрелок -ребрами. Граф, в котором направление линий не выделяется (все линии являются ребрами), называется неориентированным; граф, в котором направление линий принципиально (линии являются дугами) называется ориентированным.
Теория графов может рассматриваться как раздел дискретной математики (точнее - теории множеств), и формальное определение графа таково: задано конечное множество X , состоящее из n элементов (X = {1, 2,..., n}), называемых вершинами графа, и подмножество V декартова произведения X хХ, то есть VcX 2 , называемое множеством дуг, тогда ориентированным графом G называется совокупность ( X , V ) (неориентированным графом называется совокупность множества X и множества неупорядоченных пар элементов, каждый из которых принадлежит множеству X ). Дугу между вершинами i и j , i , j еХ, будем обозначать ( i , j ). Число дуг графа будем обозначать m ( V = ( v 1, v 2,..., v m )).
https://drive.google.com/file/d/0B2BeihKRHPZcWmNmdVB6dElyTnc/view?usp=sharing
Комментариев нет:
Отправить комментарий