Вариант № 4.

1. Найти диаметр, радиус и центр графа G.

2. Орграф задан матрицей смежности. Найти матрицу сильной связности орграфа. Выделить компоненты сильной связности. Построить реализацию графа и его компонент сильной связности.

А=

3. Используя алгоритм фронта волны, найти минимальный путь из вершины v₁ в вершину v₅ в орграфе, заданном матрицей смежности

4. Дан граф G=(V,X). V=1,2,3,4,5. X=(1,2), (1,3), (1,4), (3,4), (3,5), (4,2), (4,5), (5,2). Построить остов графа. Найти цикломатическое число графа. Выделить базис циклов графа.

5. Найти хроматическое число графа К_3,4.

Вариант № 5.

1. Дан граф G. Построить соответствующий реберный граф. Найти матрицу смежности реберного графа через матрицу инцидентности исходного графа. Определить степени вершин и число ребер реберного графа через исходный граф.

2. Найти по формуле матрицу связности графа G, заданного матрицей смежности:

3. Используя алгоритм Форда-Беллмана, найти минимальный путь из вершины v₁ в вершину v₅ в нагруженном орграфе, заданном матрицей длин дуг:  

4. Дан граф G=(V,X). V=1,2,3,4,5, X=(1,3), (1,4), (2,4), (2,5), (3,4), (3,5), (4,5), ( 5,1). Построить остов графа. Найти цикломатическое число графа. Выделить базис циклов графа.

5. Найти количество полных трехвершинных подграфов графа К_5,6.

Вариант № 6.

1. Найти диаметр, радиус и центр графа G.

2. Орграф задан матрицей смежности. Найти по формуле матрицу сильной связности орграфа. Выделить компоненты сильной связности. Построить реализацию графа и его компонент сильной связности.

А=

3. Используя алгоритм фронта волны, найти минимальный путь из вершины v₁ в вершину v₅ в орграфе, заданном матрицей смежности

4. Дан граф G=(V,X). V=1,2,3,4,5. X=(1,4), (2,3), (2,5), (3,4), (3,5), (4,2), (4,5), (5,1). Построить остов графа. Найти цикломатическое число графа. Выделить базис циклов графа.

5. Доказать, что граф Е³ является двудольным.

Ответы Часть 1

§ 1

1.5. а) AB=[-5; 8]; AB=[0; 1]; A\B=(1; 8]; B\A=[-5; 0);

A+B=[-5; 0)(1; 8];

б) AB =(-; +); AB =[0; 5]; A\B=(-; 0); B\A=(5; +);

A+B=(-;0)(5;+);

в) AB=А; AB=N; A\B=; B\A={x|x=2k–1; kN};

A+B=B\A;

г) AB=A; AB=B; A\B=; B\A={0}; A+B={0}.

1.6. (-1;3)

1.9. 140

1.10. 20

1.12. 100

1.13. а) (AB) C; б) в) г) д)

§ 2

2.4. а) Д={1,3,5,7} R={3,5,7}

^-1={(3,7), (7,3), (3,5), (5,1)}

o={(3,3), (7,7), (5,7), (1,3)}

o^-1={(3,3), (7,7), (7,5), (5,7), (5,5); (1,1)}

r^-1or={(3,3), (7,7), (5,5)}

r^-1or^-1={(3,3), (7,7), (7,5), (3,1)}

в) Д=R, R=R, r^-1=

o={(x,y)/x,yR}

г) Д={x/x=2n-1, nN}

R={y/y=2n-1, nN}

r^-1=, o=

д) Д=R, R=R

r^-1={(x,y)/x,yR и x<2y-1}

ror={(x,y)/x,yÎR и y<4x-3}

r^-1or=o^-1={(x,y)/x,yÎR}

r^-1or^-1={(x,y)/x,yÎR и x<4y-3}

e) Д=R, R=R

r^-1={(x,y)/x,yR и x=y²}

ror={(x,y)/x,yR и y=x⁴}

ror^-1={(x,y)/x,yÎR и x²=y²}

r^-1or={(x,y)|x,yÎR и x=y}

r^-1or^-1={(x,y)|x,yÎR и x=y⁴}

§ 3

3.1. а) нерефлексивное, несимметричное, нетранзитивное отношение;

б) рефлексивное, симметричное, транзитивное отношение;

в) рефлексивное, симметричное, транзитивное отношение;

г) антирефлексивное, антисимметричное, транзитивное отношение;

д) нерефлексивное, симметричное, транзитивное отношение;

е) рефлексивное, антисимметричное, транзитивное отношение;

ж) рефлексивное, симметричное, транзитивное отношение;

з) рефлексивное, симметричное, транзитивное отношение.

3.2. а) ={(4,4), (6,6), (4,6), (6,4), (-2,-2), (0,0), (-2,0), (0,-2), (3,3)};

б) ={(4,4), (6,6), (-2,-2), (0,0), (6,-2), (-2,6), (6,0), (0,6), (-2,0),

(0,-2), (3,3)}

3.3. а) [2]_1= {2}; [4]_1= {4}; [6]_1= {6}; [8]_1= {8}

A/₁= {{2}, {4}, {6}, {8}};

б) [2]_2= {2, 4}; [4]_2= {2, 4}; [6]_2= {6}; [8]_2= {8}

A/₂= {{2, 4}, {6}, {8}};

в) [2]_3= {2, 4}; [4]_3= {2, 4}; [6]_3=[8]_3= {6, 8}

A/₃= {{2, 4}, {6, 8}}

§ 4

4.1. а) отношение частичного нелинейного порядка;

б) отношение строгого нелинейного порядка;

в) отношение частичного нелинейного порядка;

г) не является отношением порядка;

д) отношение строгого линейного порядка.

r={ (a,a), (b,с) (а,b), (b,b) (c,c), (a,c) };

r – отношение строгого порядка на множестве А.

r₁={(a,b), (a,c), (a,d), (b,d), (c,d) (b,c)};

отношение строгого линейного порядка.

§ 5

5.1. а) функция;

б) не является функцией;

в) не является функцией;

г) функция;

д) не является функцией;

е) не является функцией;

ж) не является функцией;

з) функция;

и) не является функцией;

к) функция.

5.2. а) f – не инъективное, не сюръективное; g – не инъективное, сюръективное;

б) f – инъективное, не сюръективное;

в) f – инъективное, не сюръективное;

г) f – не инъективное, сюръективное;

д) f – биективное;

е) f – не инъективное, не сюръективное.