• Сетью



  • страница1/17
    Дата03.01.2019
    Размер1.68 Mb.

    Х и У. Х это множество точек, называемых вершинами


      1   2   3   4   5   6   7   8   9   ...   17
      Навигация по данной странице:
    • Сетью

    Часть VI. Элементы теории графов.
    §1. Основные понятия теории графов.
    Определение 1. Графом называется совокупность 2-х множеств Х и У. Х - это множество точек, называемых вершинами графа, а У - это множество линий попарно соединяющие вершины и называемые ребрами или дугами.
    Это определение можно сформулировать иначе: графом называется непустое множество точек (вершин) и отрезков (ребер), оба конца которых принадлежат заданному множеству точек.

    В дальнейшем вершины графа мы будем обозначать латинскими буквами A, B, C, D. Иногда граф в целом будем обозначать одной заглавной буквой.



    Определение 2. Вершины графа, которые не принадлежат ни одному ребру, называются изолированными.
    Определение 3. Граф, состоящий только из изолированных вершин, называется нуль – графом.
    Определение 4. Если рассматривается упорядоченное множество точек, т.е. на каждом ребре задается направление, то граф называется ориентированным; в противном случае граф называется неориентированным.



    Определение 5. Сетью называется граф, в каждой дуге которого поставлено в соответствие некоторое число (или несколько чисел), которое называется весом дуги или ребра (). Например, расстояние между городами, стоимость прокладки дороги, потоки (пропускная способность дуги и т.д.).

    §2. Свойства вершин и ребер графа.
    Определение 1. Ребра, имеющие одинаковые концевые точки называется параллельными .
    Определение 2. Ребро, концевые вершины которого совпадают, называется
      1   2   3   4   5   6   7   8   9   ...   17

    Коьрта
    Контакты

        Главная страница


    Х и У. Х это множество точек, называемых вершинами