Слайд 2Графом называется простейшая модель связанной системы, т. е. некоторая выделенная совокупность объектов,
![Графом называется простейшая модель связанной системы, т. е. некоторая выделенная совокупность объектов,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/965040/slide-1.jpg)
между каждой парой элементов которой установлено наличие или отсутствие связи.
Если кроме факта связи устанавливается и её направление (ориентация связи), то граф называется ориентированным.
Неориентированный граф легко моделируется ориентированным: факт наличия связи между двумя различными элементами моделируется двумя ориентированными связями – связью «туда» и связью «обратно».
Слайд 3Теория графов – наука, которая занимается изучением свойств графов и различными способами
![Теория графов – наука, которая занимается изучением свойств графов и различными способами](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/965040/slide-2.jpg)
их математического моделирования (различными способами их интерпретации).
Вершины – элементы связанной системы, составляющей граф.
Смежные вершины – две различные вершины, между которыми существует связь.
Слайд 4Один и тот же граф с различным образом помеченными вершинами называется различный
![Один и тот же граф с различным образом помеченными вершинами называется различный](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/965040/slide-3.jpg)
представитель графа. Они рассматриваются как разные объекты.
Различные представители графа изоморфны, т.е. между их вершинами существует взаимнооднозначное соответствие, сохраняющее смежность вершин.
Слайд 5Вершины можно моделировать точками на плоскости. В этом случае связь между любыми
![Вершины можно моделировать точками на плоскости. В этом случае связь между любыми](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/965040/slide-4.jpg)
двумя вершинами можно моделировать направленным или ненаправленным отрезком кривой.
Граф моделируется двумя множествами – множеством вершин и множеством отрезков, которые для удобства различают в названиях.
Направленные отрезки называются дугами, а ненаправленные ребрами.
Вершина, ограничивающая ребро называется инцидентной этому ребру (дуге), и наоборот.
Слайд 6Моделируем элементы, составляющую систему, как элементы некоторого множества вершин V, а ненаправленные
![Моделируем элементы, составляющую систему, как элементы некоторого множества вершин V, а ненаправленные](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/965040/slide-5.jpg)
связи (ребра) между некоторыми парами вершин, как двухэлементные подмножества множества вершин.
В этом случае две вершины называются смежными, если они принадлежат одному и тому же двухэлементному подмножеству. Вершина и ребро (двухэлементное подмножество) называются инцидентными друг другу, если вершина принадлежит этому ребру.
Аналогично с ненаправленными моделируются направленные связи связанной системы, как упорядоченные двухэлементные подмножества, точнее как упорядоченные пары.
Слайд 7Матрица смежности графа
Любая упорядоченная пара-дуга ( , ) i j v v
![Матрица смежности графа Любая упорядоченная пара-дуга ( , ) i j v](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/965040/slide-6.jpg)
заданного n-элементного множества вершин 1 2 { , ,..., } V v v v = n , вернее её наличие или отсутствие в описании связанной системы, однозначно определяется значением 1 или 0 соответственно на (i,j)-ом месте квадратной матрицы порядка n.
Слайд 9Графом называется фигура, состоящая из точек, называемых вершинами, и отрезков, соединяющих некоторые
![Графом называется фигура, состоящая из точек, называемых вершинами, и отрезков, соединяющих некоторые](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/965040/slide-8.jpg)
из этих вершин. Соединяющие отрезки могут быть направленными (дугами - случай ориентированного графа), ненаправленными (ребрами - случай неориентированного графа), прямолинейными или криволинейными.
Отрезок, соединяющий вершину с самой собой, называется петлей.
Слайд 11Матричное 1 – ориентированным графом называется множество (класс) квадратных (0,1)-матриц, перестановочно подобных
![Матричное 1 – ориентированным графом называется множество (класс) квадратных (0,1)-матриц, перестановочно подобных](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/965040/slide-10.jpg)
между собой. (Две квадратные матрицы называются перестановочно подобными (P-подобными), если от одной к другой можно перейти с помощью перестановки рядов, т.е. с помощью перестановки строк и такой же перестановки столбцов.)
Матрицы, в этом определении, называются матрицами смежности графа.
Слайд 12Матричное 2 – обыкновенным неориентированным графом называется множество (класс) (0,1)-матриц инцидентности B,
![Матричное 2 – обыкновенным неориентированным графом называется множество (класс) (0,1)-матриц инцидентности B,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/965040/slide-11.jpg)
перестановочно эквивалентных между собой.
Матрицы B характеризуются тем, что у них все столбцы различные и у каждого столбца только два элемента равны 1, а все остальные элементы столбца равны 0.
Две матрицы инциденций называются перестановочно эквивалентными, если одна может быть получена из другой с помощью некоторой перестановки строк и некоторой перестановки столбцов.
Слайд 13Матричное 3 – обыкновенным ориентированным графом называется множество (класс) ориентированных матриц инцидентности
![Матричное 3 – обыкновенным ориентированным графом называется множество (класс) ориентированных матриц инцидентности](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/965040/slide-12.jpg)
B, перестановочно эквивалентных между собой. Ориентированные матрицы инцидентности B характеризуются тем, что у них все столбцы различные и у каждого столбца только два элемента отличны от нуля, один из которых равен единице, а другой – минус единице.
Слайд 14Замечание 1. Матричные определения 1, 2 и 3 отличаются от предыдущих тем,
![Замечание 1. Матричные определения 1, 2 и 3 отличаются от предыдущих тем,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/965040/slide-13.jpg)
что определяют граф как класс объектов (матриц). Это объясняется тем, что при матричном моделировании связей приходится указывать привязку связываемых элементов двух экземпляров одного множества и двух разных множеств к месту в матрице.
Замечание 2. Матричное определение 1 позволяет включить в определение графа как псевдографы (графы с петлями), так и неориентированные графы.
Замечание 3. Матричные определения 2 и 3 не позволяют обобщения графа на псевдографы, однако если в этом определении отказаться от требования различия столбцов мы получим обобщение определений обыкновенных графов на мультиграфы (графы с кратными связями).
Замечание 4. Отношение перестановочного подобия и отношение перестановочной эквивалентности являются частными случаями бинарного отношения эквивалентности и позволяют разбить соответствующие множества на непересекающиеся подмножества эквивалентных между собой элементов (матриц).