Теория графов. Основные понятия и определения.
№1. Общие сведенья графах.
Фигура образованная совокупностью точек и линий является математически объектом называемом графом или не ориентированным графом.
Если ввести данный граф направление с помощью стрелок, обозначающих одностороннее движение, так что бы из любой точки х была доступна любая точка у, то мы получим ориентированный граф или орграф.
Будем определять орграф парой VA, где V – некоторое множество вершин орграфа;
А – множество упорядоченных пар элементов из V (дуг).
В реальном мире может существовать не один граф, а несколько графов. Граф связен если он состоит из единственной части или что эквивалентно если для каждой пар точек (х;у) цепь из линий соединяющих точки х и у. α – мост, соединяющий 2 части графа.
Мост – это линия, в связанном графе удаление которой превращает этот граф в несвязный.
Не каждая линия, соединяющая различные части графа, может являться мостом.
№2. Орграфы и наличие связей в них.
Связь орграфов может быть сильной или слабой, в зависимости от возможности достичь одну вершину из другой. Орграф называется сильно связанным или сильным, если для каждой пары вершин U и V, вершина U достижима из вершины V, и вершина V достижима из вершины U.
Орграф называется односторонне связанным или односторонним если для каждой пары вершин U и V хотя бы одна достижима из другой.
Каждый сильно связанный граф является одновременно и односторонне связанным, но не наоборот.
Орграф называется слабосвязанным или слабым, если каждая пара вершин U и V соединима таким образом.
№3. Знаковые графы.
Знаковым графом или орграфом называется структура с ребрами или дугами, к которым добавлен знак + или -. Знак пути, то есть перемещение между вершинами определяется как произведение знаков входящего в него дуг или ребер, если знак заменить на +1 и -1.
Для того, что бы собрание людей стало группой необходимо, что бы выполнялись следующие условия:
некоторая продолжительность существования;
наличие общей цели или целей;
развитие хотя бы начальной групповой структуры.
Для представления группы в виде знакового графа или орграфа необходимо обозначить взаимоотношения между членами группы виде плюсов, означающих симпатию, общение, общность взглядов, и минусов – антипатия, избегание, несогласие.
№4. Баланс.
Малая группа представляется ее знаковым графом и группа читается сбалансированной, если каждый цикл в ее знаковом графе положителен. Циклом называется замкнутая цепь U1, e1,U2,e2…Ut,et,Um,em в которой вершины и ребра различны.
Знаковый граф соответствующий сбалансированной группе называется сбалансированным. Знаковый граф сбалансирован тогда и только тогда когда его вершины можно разделить на два класса, так что каждое ребро внутри класса имеет знак + или -.Создание модели на основе графов сводится к построению несбалансированного графа, изменению одного или нескольких знаков нем и получении сбалансированного графа.
Лекция №13