Контрольная «Комбинаторика и теория графов»

Задания к индивидуальной расчетной работе («Комбинаторика и теория графов»)

№1.

В классе 30 человек, каждый из которых изучает иностранный язык. 20

человек изучает английский, 15 – французский и 10 – немецкий. При этом в

группах изучающих по два языка насчитывается по 8 человек. Сколько

человек изучает все три языка?

№2

Семь девушек водят хоровод. Сколькими различными способами они могут

встать в круг?

№3

В зависимости от исходных данных.

Задать граф, представленный множеством вершин и ребер, графически и

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

Задать граф, представленный матрицей инцидентности, алгебраически,

графически и матрицей смежности, преобразовать граф в плоский, вычислить

степени его вершин.

Задать граф, представленный графически, множеством вершин и ребер и

матрицами, преобразовать граф в плоский, вычислить степени его вершин

	a	b	c	d	e	f	g	h	i
1	0	1	0	0	1	0	0	1	0
2	1	1	0	1	0	0	0	0	1
3	0	0	1	0	0	0	1	0	1
4	0	0	0	0	1	1	1	0	0
5	1	0	0	0	0	1	0	1	0
6	0	0	1	1	0	0	0	0	0

№4

Дан неориентированный граф. Определить

‒ диаметр и радиус этого графа;

‒ центры графа. 𝑉 = {1; 2; 3; 4; 5; 6};

𝐸 = {(1; 2); (1; 3); (1; 4); (2; 5); (3; 6);(3; 4); (4; 6); (5; 3)}

№5.

Определить, сколькими способами можно попасть из пункта х в пункт у и

найти кратчайший маршрут из х в у.