Понятие компоненты связности

Пример.

Второй способ доказательства формулы бинома Ньютона.

В2.4. Бином Ньютона

Пример 2.

Число неотрицательных решений в целых числах уравнения равно , ведь всякое решение данного уравнения можно трактовать, как сочетание с повторениями, содержащее элементов первого типа (), элементов второго типа (), …,элементов n го типа (), .

Утверждение. Справедлива формула (формула бинома Ньютона)

.

Чтобы получить произведение вида нужно из имеющихся скобок отобрать скобок, из которых выбирается сомножитель а, в оставшихся k скобках выбрать в качестве сомножителя b. Но число способов выбрать k скобок из п имеющихся равно . Следовательно, = , что и требовалось.

Следствия.

1. При =1, =1: (1 + 1)ⁿ= 2ⁿ = .

2. При = 1, = -1: (1 - 1)ⁿ = 0= (-1)^k .

2⁴ = 16 =1 + 4 + 6 + 4 + 1.

0 = 1 - 4 + 6 - 4 + 1.

Любой граф может быть однозначно разделен на максимальные связные подграфы, которые называются его компонентами связности.

Компонентой связности С(Vi) называется подграф графа G, порожденный С(Vi).

Компонентой сильной связности орграфа G называется его максимальный сильно связный подграф

Пусть G1,G2… - компоненты связности, порожденные на множестве вершин V1,V2,… тогда:

«Для всякого I, для всякого j вершина i!=вершине j»

«Подмножества не содержат общих вершин»(пересечение равно 0)

«Объединение подмножеств вершин составляет множество вершин графа»

Граф G=(V,U), связен тогда и только тогда, когда множество его вершин нельзя разбить на два пустых подмножества V1 и V2 так, что обе граничные точки каждого ребра находятся в одном и том же подмножестве.

//К следующей пятнице: