Ewrerwer

  • 14 мая 2012 г.
  • 1643 Слова
1.Что называется графом?
Графом G называется пара множеств (V,E) , где V-конечное множество элементов которые называются вершинами, E состоит из пар множеств элементов V. Элементы множества E называются ребрами.
2.Геометрическое представление графа.
Геометрическое представление графа: Вершины изображаются точками или кружочками на плоскости, если две вершины образуют ребро, то соответствующуюпару точек соединяют линией.
3.Какой граф называется ориентированным?
Граф состоящий только из дуг называется ориентированным.
4.Какой граф называется неориентированным?
Граф состоящий только из ребер называется неориентированным.
5.Какой граф называется смешенным?
Рассматриваются также смешенные графы состоящие из ребер и дуг.
6.Какие вершины называются смежными?
Если вершина V1 и V2соединены ребром E ,то говорят что вершина V1 и V2: а)смежные; б)инциндентны ребру E.
7.Что значит: вершина инциндентна ребру?
8.Что называется петлей?
Ребро называется петлей если оно начинается и заканчивается в одной и той же вершине.
9.Что называется степенью вершины?
Степенью вершины называется число ребер которым она инциндентна.
10.Какая вершина называется ветвящейся?
Если степень вершины> или = 3, то вершина называется ветвящейся.
11.Какая вершина называется висячей?
Если степень вершины = 1,то вершина называется висячей.
12.Какая вершина называется изолированной?
Если степень вершины = 0, то вершина называется изолированной.
13.Что называется маршрутом?
Маршрутом в графе называется такая последовательность его ребер в которой начало каждого последующего ребра совпадает сконцом предыдущего.
14.Что называется цепью?
Если в маршруте не повторяются ребра, то он называется цепью.
15.Что называется простой цепью?
Если в цепи не повторяются вершины, то такая цепь называется простой цепью.
16.Что называется циклом?
Цепь в которой первая и последняя вершина совпадают называется циклом.
17.Что называется пустым графом?
Граф который не имеет ни одного ребра называетсяпустым графом.
18.Какой граф называется связным?
Граф называется связанным если любые 2 его вершины соединены простой цепью.
19.Что называется деревом?
Связный граф не содержащий циклов называется деревом.
20.Что называется лесом?
Граф не имеющий циклов называется лесом.
21.Что называется полным графом?
Граф у которого каждая пара вершин соединена ребром называется полным и обозначаетсяKn, где n-количество вершин.
22.Какой граф называется мультиграфом?
Если хотя бы одну пару вершин соединяют несколько ребер, то такой граф называется мультиграфом.
23.Что называется подграфом?
Граф H называется подграфом G если вершины и ребра H принадлежат графу G.
24.Что называется остовным подграфом?
Подграф графа G содержащий все его вершины называется остовным.
25.Что называетсяобъединением графов?
Объединением графов G1 и G2 называется граф G1∪G2, который содержит вершины и ребра, которые принадлежат хотя бы одному графу.
26.Что называется пересечением графов?
Пересечением графов G1 и G2 называется граф G1∩G2, который содержит вершины и ребра, которые являются общими для этих графов.
27.Что называется дополнением графов?
Дополнением графов G1 и G2называется граф G, которыйимеет тоже множество вершин что и граф G, а ребра соединяют две его вершины только в том случае если в исходном графе ребро между указанными вершинами отсутствуют.
28.Что представляет собой матрица инциндентности неориентированного графа?
Матрица инцендентности – прямоугольная матрица R размером nxm, где n-количество вершин, m-количество ребер(дуг), строчками поставлены в соответствии вершины,а столбцам ребра(дуги).
Если граф неориентированный, то его элементы ri j =1, если вершина ϑi инцидентна ei в противном случае ri j=0.
29.Что представляет собой матрица инциндентности ориентированного графа?
Матрица инцендентности – прямоугольная матрица R размером nxm, где n-количество вершин, m-количество ребер(дуг), строчками поставлены в соответствии вершины, а столбцам...
tracking img