У назівається довжина найкоротшого маршруту, что з єднує їх.
Граф назівають зв'язного, ЯКЩО будь-яку пару его вершин сполучає який-небудь маршрут. Будь-який загальний граф можна Розбита на підграфі, КОЖЕН з якіх виявило зв'язного. Мінімальне число таких зв'язковий компонент назівається числом зв'язності графа и позначається через з ( G)
1.5 Орієнтовані графи (орграф)
Означення 1.5.1.1 Орієнтованім графом (орграфом) G = (V, E), назіваеться система, яка Складається з непорожньої множини V І непорожньої множини U впорядкованим пар ЕЛЕМЕНТІВ з множини V. Елементи множини V назіваються вершинами орграфа G , а елєменти множини Е - дугами орграфа G = ( V , E ). Отже, дуга - це впорядкована пара вершин. Відповідно, V назівається множини вершин и Е - множини дуг орграфа G .
Если е = ( v < span align = "justify">, w ) - дуга, то вершина v назівається качаном , а вершина w - кінцем дуги е . Кажуть, что дуга е веді З вершин v у вершину w або виходе з v и заходити у ...
