Число потоков в графе

Содержание

Слайд 2

n = 4

 

N- число потоков на графе.

 

n = 4 N- число потоков на графе.

Слайд 3

n = 3

 

N- число потоков на графе G.

 

G

n = 3 N- число потоков на графе G. G

Слайд 4

n = 3

 

N- число потоков на графе G.

 

G

~

n = 3 N- число потоков на графе G. G ~

Слайд 5

n = 3

 

N- число потоков на графе G.

 

G

~

n = 3 N- число потоков на графе G. G ~

Слайд 11

1. На каком наименьшем количестве ребер графа G достаточно задать значение потока

1. На каком наименьшем количестве ребер графа G достаточно задать значение потока
так, чтобы поток был определен однозначно? G = V7

g – циклическое число графа G, показывающее ,то сколько ребер нужно удалить из графа G, чтобы он перестал иметь циклы в своей структуре.
g = R – V + 1, где R – число ребер в графе всего.
V – число вершин в графе.

 

 

2)

3)

 

 

 

 

 

 

 

Слайд 12

13. Найдите все корни многочлена P(x) = x3 + x2 + 2,

13. Найдите все корни многочлена P(x) = x3 + x2 + 2,
принадлежащие GL(3, F3) , F3={0,1, 2};

Решение:

1) Составим нормальную форму Фробениуса (НФФ) .

 

 

2) Будем рассматривать P(M) как минимальный многочлен для M.

x3 + x2 + 2 = 0

 

 

 

 

 

Слайд 13

12. Найдите все корни многочлена x3 + x2 + 2, принадлежащие GL(3,

12. Найдите все корни многочлена x3 + x2 + 2, принадлежащие GL(3,
F3).

Продолжение:

P(M)= M 3 + M 2 + 2E =? 0

 

3) Проверим,что P(M)= 0:

 

P(M)= M 3 + M 2 + 2E = 0

 

 

 

 

 

 

Слайд 14

12. Найдите все корни многочлена x3 + x2 + 2•1, принадлежащие GL(3,

12. Найдите все корни многочлена x3 + x2 + 2•1, принадлежащие GL(3,
F3).

Продолжение:

P(M)= M 3 + M 2 + 2E =? 0

 

3) Проверим,что P(M)= 0:

 

 

 

 

 

 

Слайд 15

12. Найдите все корни многочлена x3 + x2 + 2•1, принадлежащие GL(3,

12. Найдите все корни многочлена x3 + x2 + 2•1, принадлежащие GL(3,
F3).

Продолжение:

P(M)= M 3 + M 2 + 2E =? 0

 

3) Проверим,что P(M)= 0:

 

 

 

 

 

 

 

 

 

 

 

 

 

Слайд 16

12. Найдите все корни многочлена x3 + x2 + 2•1, принадлежащие GL(3,

12. Найдите все корни многочлена x3 + x2 + 2•1, принадлежащие GL(3,
F3).

Продолжение:

P(M)= M 3 + M 2 + 2E =? 0

 

3) Проверим,что P(M)= 0:

 

 

 

 

 

 

 

 

 

Слайд 17

12. Найдите все корни многочлена x3 + x2 + 2, принадлежащие GL(3,

12. Найдите все корни многочлена x3 + x2 + 2, принадлежащие GL(3,
F3).

Продолжение:

4) Воспользуемся схемой Горнера для определения остаточного многочлена:

 

 

 

 

 

 

 

 

 

 

 

 

 

Слайд 18

Найдите все корни многочлена x2 + 3x+ 1, принадлежащие GL(2, F7).

 

 

 

 

 

 

 

 

 

 

 

 

Найдите все корни многочлена x2 + 3x+ 1, принадлежащие GL(2, F7).

Слайд 19

Пусть I = (18), J = (24) — идеалы в Z .

Пусть I = (18), J = (24) — идеалы в Z .
Найдите а) I ∩ J, б) I + J.

Z

 

 

 

I = (18) = {0,18, 36, 72}

Z

36•8 = 288 = 18•16

 

I ∩ J

I (18) ∩ J (24) = {18k, k ∈ Z} ∩ J {24k, k ∈ Z} = { 72k, k ∈ Z} = S(72)

J = (18) = {0,18, 36, 72}

 

 

 

I (18) + J (24) = {18k, k ∈ Z} + J {24k, k ∈ Z} = {18k + 24k, k ∈ Z}

I (18) + J (24) = {18k, k ∈ Z} + J {24k, k ∈ Z} = {b = 18n + 24m = 6L= 6(3n + 4m), n, m , L ∈ Z} = S(6)

18 + 48 = 66 = 6•11

18•2 + 24•2 = 36 + 48 = 84 = 6•7•2

I + J

Ответ: I(18) ∩ J(24) = S(72), I(18) + J(24) = S(6)

Имя файла: Число-потоков-в-графе.pptx
Количество просмотров: 37
Количество скачиваний: 0