Партнерка на США и Канаду по недвижимости, выплаты в крипто

  • 30% recurring commission
  • Выплаты в USDT
  • Вывод каждую неделю
  • Комиссия до 5 лет за каждого referral

2

5

1

3

4

n

2.) Одна из цепочек замкнулась на 3, тогда из вершины с номером 2 строим цепь 2-4. Ни одна из этих цепей не замкнется на 4-ю вершину (т. к. граф планарный!). Меняем цвета 2 и 4 в этой цепи. И красим n+1-ю вершину в цвет 2.

Таким образом, то, что пяти красок достаточно, доказано.

Возвращаясь к четырем краскам следует сказать, что американскими математиками была доказана теорема, о том, что четырех красок достаточно. Однако, в этом доказательстве есть шаги, связанные с очень большими переборами вариантов, выполненные с использованием компьютера (пойди проверь). Так что с точки зрения «пуританской» математики можно считать, что теорема пока не доказана…

4.8. Определение путей в графе

a b

g

c

f

e d

Требуемые результаты получаются путем перемножения матриц смежности графа.

M - матрица смежностей, показывает пути длиной в 1 в данном графе.

a

b

c

d

e

f

g

a

1

1

b

1

c

d

1

e

1

1

f

1

1

g

1

a

b

c

d

e

f

g

a

1

1

b

1

c

d

1

e

1

1

f

1

1

g

1

M M

Матрица M2 дает все пути длиной в 2

a

b

c

d

e

f

g

a

1

b

c

d

1

e

1

f

1

1

g

Матрица Мn - пути длиной в n.

Если Мi - нулевая матрица, то наибольший путь в графе имеет длину i - 1.

Для определения наличия путей между двумя вершинами можно использовать «транзитивное замыкание» матриц

M* = M1 È M2 È M3 ...

Непустая клеточка ij будет говорить о наличии пути из i-ой вершины в j-ую.

4.9. Приведение графа к ярусно-параллельной форме

Эти рассуждения имеют смысл для ориентированных графов без контуров.

Граф находится в ярусно-параллельной форме (ЯПФ),

если в нулевом ярусе размещаются вершины, имеющие нулевую полустепень захода, в i-том ярусе - вершины, в которые заходят дуги только из предыдущих ярусов, причем хотя бы одна дуга из (i - 1)-го яруса.

Пусть дан произвольный граф без циклов.

a

h b

g c

f d

e

a

b

c

d

e

f

g

h

a

1

b

c

1

d

1

1

e

1

1

f

1

g

1

1

h

1

1

Алгоритм приведения к ЯПФ:

1. Матрица смежности графа просматривается, и в очередной ярус выбираются вершины с нулевой полустепенью захода, соответствующие нулевым столбцам.

2. Строки, соответствующие выбранным на предыдущем шаге вершинам, обнуляются.

3. Осуществляется возврат к шагу 1, до полного исчерпания матрицы.

4. Прорисовываются дуги.

В результате, вышеприведенный граф примет вид:

d

 

e h

g f

Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29