Опред-е графа и его осн-е характер-ки. Вершины и ребра. Графич-я интерпр-я графа. Смежность и инцидентность. Локальная степень. Подграф. Полный подграф

Пусть А – любое мн-во. Обозначим через V(A) – мн-во всех неупорядоченных пар его различ.эл-тов. #A= {1,2,3}. Тогда V(A)={(1,2);(1,3);(2,3)}. Если мн-во А={1,2}, тогда V(A)={(1,2)}. Если A={1}, тоV(A)=Æ. Когда в записи V(A) указ-ся пара (1,2), то это обозначает одно и то же, что и пара (2,1), т.к. она не упорядоченная. Графом наз-ся пара мн-в Г=[A,B], где А – любое непустое мн-во, ВÍV(A). Эл-ты из мн-ва А наз-ся вершинами графа, а эл-ты из В – его ребрами. Граф, содержащий только ребра, называется неориентированным; граф, содержащий только дуги – ориентированным или орграфом. Геом. интерпретация графа: пусть Г=[A,B] – некоторый граф. А={a₁,a₂,…,a_p}, В={в₁,в₂,…,в_q}. Фиксируем на плоск-ти проивол.образом р-точек и назовем их А1, А2, …, Ар. Затем д/кажд.пары (а_i, а_j)ÎВ проведем отрезок, соед-щий дан.вершины. Если в некотором графе пара вершин а_i, и а_j Î одному ребру, то они наз-ся смежными. В этой ситуации каждый из них наз-ся инцидентной ребру (а_i, а_j), а ребро (а_i, а_j) - инцидентно кажд.вершине а_i, и а_j. Кол-во ребер, инцидентных дан.вершине А, наз-ся ее степенью или локал.степенью графа в вершине А; обознач-е d(a) – степень вершины А. В любом графе кол-во вершин нечетной степени обяз-но четно. Пусть даны Г1=[A1,B1] и Г2=[A2,B2] – два графа таких, что А1ÍА2, а В1ÍВ2. Тогда говорят, что граф Г1 явл-ся подграфом Г2. Если в некотором графе Г=[A,B] мн-во ребер В таково, что В=V(A), то дан.граф наз-ся полным. Если в полном графе число вершин р, то ребер будет: (р(р-1)/2). Пусть Г=[A,B] – граф и А={a₁,a₂,…,a_p} – его вершины. Построим квадрат.матрицу, состоящую из эл-тов М=(m_ij), где i,j=1,2,…,р.

Эта матрица наз-ся матрицей смеж-тей графа. Она симметрична. Сопоставим графу Г=[A,B] еще одну матрицу. А={a₁,a₂,…,a_p} – вершины, В={в₁,в₂,…,в_q} – ребра. Определим матрицу N=(n_ij) след.образом:

Такая матрица наз-ся матрицей инциденций графа. Дан.матрица зависит от того, как занумерованы ребра. Если в графе все вершины имеют степень 0, то матрицы инциденций не сущ-ет.