Добавил:

ivanov666 Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Владимирский государственный университет им. Столетовых

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

Учебное пособие для студентов заочного факультета по дисциплине «Дискретная математика» (90

..pdf

Скачиваний:

Добавлен:

15.11.2022

Размер:

1.08 Mб

Скачать

☆

<<< < Предыдущая 1 2 3 45 / 55

130.Число способов выбора 2 дам из колоды в 36 карт при случайном извлечении трех карт - C42C321 .

131.Число способов выбора 3 тузов из колоды в 36 карт при случайном извлечении трех карт - C43 .

132.В группе 25 студентов. Из них требуется выбрать старосту, заместителя старосты и финорга. Это можно сделать A253 способами.

133.Cnn k Cnk .

134.

Cn0

Cn1 ...

Cnn

2n .

b n

135.

Cnk an k bk .

b n

1 k Cnk an

136.

k bk .

137.

Общий член разложения

b n

(формулы Ньютона) T

C k an k bk .

k 1

138.

Общий член разложения

b n T

1 k Ck an k bk .

139.

Cn0

Cn2 ...

Cn2l

Cn1

Cn3

...

Cn2l 1 .

140.

Cnk

Cnk 1

Cnk

11 .

141.

Строка треугольника Паскаля с номером n Cno Cn1 ... Cnn .

142.

x ...

xn1 xn2

...xnk .

... n

n n !n

!...n

! 1

1 2

143.

Пусть N предметов могут обладать свойствами

1 ,

2 ,...,

n . N i - число

предметов, обладающих свойством

i , i

1,..., n , N

- число предметов, не

обладающих свойством

i ,

1,..., n . Тогда

	N	N	1	N	2	...	N	n	N	1	2
			1		2			n		1	2
N 1 2 ... n	N	n 1 n		N	1 2	3	... N		n 2 n 1		n
		1 n N		1 2 ...	n .

N 1 3 ...

...

144. Пусть N предметов могут обладать свойствами	1 ,	2 ,..., n . N i - число
предметов, обладающих свойством i , i 1,..., n , N	i	- число предметов, не

обладающих свойством i , i 1,..., n . Тогда формула включения и исключения

	N	N	1	N	2	...	N	n	N	1	2
			1		2			n		1	2
N 1 2 ... n	N	n 1 n		N	1 2	3	... N		n 2 n 1		n
		1 n N		1 2 ...	n .

N 1 3 ...

...

145. Беспорядок – это такая перестановка n элементов, при которой ни один элемент не остается на своем месте.

		1	1	1		1 n
146. Число беспорядков из n элементов Dn	n! 1				...		.
146. Число беспорядков из n элементов Dn	n! 1				...		.
		1!	2!	3!		n!

147.	Число перестановок, при которых r		элементов остаются на своем месте, а
остальные n		r меняются местами D	C r D	.
		n,r	n n r
148.	Метод рекуррентных соотношений – это метод решения задачи
сведением ее к аналогичной для меньшего числа предметов.
149.	Линейное рекуррентное соотношение - un k a1un k 1 a2un k 2 ... an un .
150.	Частное решение линейного рекуррентного соотношения ищут в виде
un	rn .
151.	V G - множество вершин графа G . Пара xi , x j называется ребром графа
G , если xi , xj		V G .

152.Граф G имеет 5 ребер.

153.Граф G имеет 5 вершин.

154.Граф G имеет 5 вершин.

155. Вершины xi и x j графа G называют смежными, если xi , x j E G .

156.В графе G все вершины, смежные вершине x2 - x1 , x3 , x5 .

157.Два ребра графа G называют смежными, если они инцидентны одной вершине.

158.	В графе G все ребра, смежные ребру x1 , x2 -			x1 , x4	, x2 , x3 ,	x2 , x5 .
159.	Вершина xi		графа G инцидентна ребру xi , x j	E G .
160.	Ребро xi , x j		инцидентно вершине xi и вершине x j .
161.	Вершина xi		графа G инцидентна ребру xi , x j	E G и xi , xk		E G .
162.	В графе G все вершины, инцидентные ребру			x2 , x5	- x2 , x5 .
163.	В графе G все ребра, инцидентные вершине x5 - x2 , x5 , x4 , x5					, x5 , x6 .
164.	Ребро xi , x j		графа G называются неориентированным, если
	xi , x j	x j , xi .
165.	Нуль-граф – это граф, который состоит из изолированных вершин.
166.	Ребро	xi , x j	графа G называется петлей, если xi		x j .

167.Граф называется ориентированным, если все ребра графа ориентированы..

168.Граф называется неориентированным, если все ребра графа неориентированы.

169.Граф называется смешанным, если в графе есть как ориентированные, так

инеориентированные ребра.

170.Полный граф – это граф, содержащий все допустимые ребра.

171.Изоморфизм двух графов – это взаимно однозначное соответствие между их вершинами и взаимно однозначное соответствие между их ребрами, сохраняющее отношение инцидентности.

172.Матрицей смежности неориентированного графа G с n вершинами

называется матрица A G		,		1, если вершины xi и x j смежны,
называется матрица A G	ij	,	ij	0 в противном случае.
		n n		0 в противном случае.
		n n

173. Матрицей смежности ориентированного графа D с n вершинами

					1, если вершины xi и x j смежны,
называется матрица A D		ij		, ij	и xi		- начало дуги,
			n	n
					0 в противном случае.
174.	Матрицей инцидентности неориентированного графа G с n вершинами и
										1, если вершина xi инцидентна
m ребрами называется матрица B G									, ij	ребру a j ,
m ребрами называется матрица B G						ij	m n		, ij	0 в противном случае,
										0 в противном случае,

										или если a j - петля.
175.	Матрицей инцидентности ориентированного графа D с n вершинами и m
										1, если вершина xi инцидентна
										ребру a j , xi - начало дуги,
ребрами называется матрица B D							,			-1, если вершина xi
ребрами называется матрица B D					ij	m n	,	ij		инцидентна ребру a j , xi - конец дуги,
					ij			ij

0 в противном случае, или если a j - петля.

176. A G	ij	- матрица смежности неориентированного графа G . Тогда
		n n

при i 1,..., n ,		ij	ji .

177.Степень вершины xi графа G ( xi ) - число ребер, инцидентных вершине

xi .

178.	Положительная полустепень вершины xi орграфа D						( xi ) - число дуг,
исходящих из вершины xi .
179.	Отрицательная полустепень вершины xi орграфа D						( xi ) - число дуг,
заходящих в вершину xi .
180.	Для вершины xi орграфа D выполняется равенство						(xi )	xi	xi .
						n
181.	В графе D	V D	n ,	E D	m .	xi 2m .

182.В графе D число вершин нечетной степени четно. 0.

183.	Граф G называется однородным (регулярным), если i, i 1,..., n xi r .
184.	Однородный граф G с	xi	0 состоит из изолированных вершин.
185.	Однородный граф G с	xi	1 представляет собой объединение
изолированных отрезков.
186.	Однородный связный граф G с xi 2представляет собой

многоугольник.

187.Неориентированный граф G называется связным, если для любых двух вершин существует маршрут, связывающий эти вершины.

188.Ориентированный граф D называется несвязным, если граф D не является слабо связным.

189.Маршрут в неориентированном графе G - последовательность попарно смежных ребер.

190.	Орграф D называется сильно связным, если для любых двух вершин xi ,
x j	существует путь из xi в x j и путь из x j в xi .
191.	Орграф D называется односторонне связным, если для любых двух

вершин xi , x j существует по крайней мере путь из xi в x j или путь из x j в xi .

192.Орграф D называется слабо связным, если для любых двух вершин xi , x j существует по крайней мере маршрут из xi в x j .

193.Маршрут в неориентированном графе – последовательность попарно смежных ребер G .

194.Расстояние между двумя вершинами в неориентированном графе G - длина кратчайшей цепи, соединяющей эти вершины, или наименьшее число ребер, соединяющих эти вершины.

195.

Условный радиус графа G относительно вершины c r(G) max d (c, x) .

x V (G )

196.

Радиус графа G r(G)

min r

c .

c V (G )

197.

Центр графа G C x

r G .

V G

r c

198.

Диаметр графа G d (G)

max r c .

c V (G )

199.

- число вершин графа G ,

E G

- число ребер графа G .

R G

V G

число областей, на который граф G разбивает плоскость. Эйлерова

характеристика графа G

V G

E G

R G

200.

Эйлерова характеристика связного планарного графа равна 2.

<<< < Предыдущая 1 2 3 45 / 55

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]