1. Понятие множества. Конечные и бесконечные множества, пустое множество. Подмножество: количество подмножеств конечного множества

30. Матрица смежности.
Матрица смежности графа G, называется квадратная матрица A(G)=[aij] порядка n, у которой элементы aij равны. aij равна: 1, если (ViVj)єx; 0, если (ViVj)∉x; k, если (ViVj)єx – k раз.
31. Путь в графе. Цикл в графе. Связный граф.
Пусть дан не ориентированный граф G (V, X). Последовательность V1x1V2x2,…,xkVk+1 (k=>1), в которой чередуются вершины и ребра, называется маршрутом, соединяющим вершины V1 и Vk+1, причем V1 – начальная, Vk+1 – конечная, а V2 … Vk – внутренние. Одна и та же вершина в маршруте может быть одновременно начальной, конечной и внутренней. Количество ребер в маршруте называется длиной маршрута. Все маршруты можно разделить на 2 группы: не замкнутые, у которых начальные и конечная вершина совпадают. Замечание: в любом графе G можно указать минимум один замкнутый маршрут. Не замкнутый маршрут, в котором все ребра попарно различны, называются цепью. Цепь, в которой все вершины попарно различны, называются простой цепью. Замкнутый маршрут, в котором все ребра попарно различны, называется циклом. Цикл в котором все вершины попарно различны, называется простым циклом. Утверждение: если в графе можно задать цикл, то одновременно можно указать и простой цикл. В любом псевдографе можно указать цикл. Пусть дан ориентированный граф G (V, X). Последовательность V1x1V2x2,…,xkVk+1 (k=>1), в которой чередуются вершины и ребра, называется путем, соединяющим вершины V1 и Vk+1. Все пути делятся на замкнутые и незамкнутые. Не замкнутый путь, в котором все дуги попарно различны, называется цепью. Цепь, в которой все вершины попарно различны, называется простой цепью. Замкнутый путь, в котором все дуги попарно различны, называется контуром. Контур, в котором все вершины попарно различны, называется простым. Граф G называется связным, если для любых его 2-х вершин Vi и Vj существует маршрут их соединяющий. Граф, не являющийся связным, называется несвязным.
32. Компоненты связности графа. Степень вершины. Теорема о сумме степеней вершин графа.
Пусть дан граф D(V, X). Говорят, что вершина Vj орграфа D достижима из вершины Vi, если Vj=Vi или существует путь из Vi в Vj. Замечание: если все вершины орграфа соединены контуром или простым контуром, то все его вершины являются достижимыми. Орграф D называется сильносвязным, если для любых 2-х его вершин существует путь из одной в другую. Орграф называется односторонне связным, если для любых его 2-х вершин, по крайней мере одна достижима из другой. Компонента сильной связности орграфа D называется его сильносвязным подграфом, не является собственным подграфом, никакого другого сильносвязного подграфа D. Компонента связности связным графе G получается путём удаления последовательного удаления в графе по одному ребру не нарушающему связность графа. Степенью вершины v графа называется число дельта(v) ребер инцидентных вершине v. Замечание. В случае не ориентированного псевдографа вклад каждой петли в степень вершины равен 2. Полустепенью исхода вершины v орграфа D называется число дельта+(v) дуг исходящий из вершины v. Полустепенью захода вершины v орграфа D называется число дельта-(v) дуг заходящих в вершину v. Замечание. В случае ориентированного псевдографа вклад каждой петли равен 1 и в полустепень исхода и в полустепень захода.
34. Методика выделения компонент связности в графе. Расстояние между вершинами в графе: определение, свойства, методика нахождения. Радиус и диаметр в графа. Центральные вершины.
Граф G называется связным, если для любых его 2-х вершин Vi и Vj существует маршрут их соединяющий. Граф, не являющийся связным, называется несвязным. Компонента связности в связном графе G получается путём последовательного удаления в графе по одному ребру не нарушающему связность графа. Пусть дан граф G(v, x). Если граф связный, то любые его две вершины можно соединить маршрутом, и если таких маршрутов несколько, то среди них всегда можно указать минимальный маршрут, соединяющий вершины vi и vj. Обозначим длину минимального маршрута через d(vi vj) и договоримся, что кратчайшее расстояние d(vi vi)=0.
d(vi vj)=бесконечность, когда нет маршрута соединяющего данные вершины.
Расстояние между вершинами графа vi и vj будем называть величину d(vi vj) конечную или бесконечную. Величина d(G)=max d(vi vj) является конечной и называется диаметром графа G. Величина vi€V ч(vi)=max d(vi vj) называется максимальным удаление от вершины vi в графе G. Радиусом графа G называется величина ч(G)=min ч(vi). Любая вершина графа G для которой выполняется условие ч(G)=ч(v) называется центром графа.