Главная страница
Навигация по странице:

  • Матрица инцидентности

  • Матрица связности

  • Дискретная математика Сборник заданий 2010. 1 Множества и отношения 1 Основные понятия и определения


    Скачать 1.67 Mb.
    Название1 Множества и отношения 1 Основные понятия и определения
    АнкорДискретная математика Сборник заданий 2010
    Дата12.02.2022
    Размер1.67 Mb.
    Формат файлаdoc
    Имя файлаДискретная математика Сборник заданий 2010 .doc
    ТипДокументы
    #359373
    страница7 из 8
    1   2   3   4   5   6   7   8

    2.3 Примеры выполнения заданий

    Задание 1





    1. Ориентированный псевдограф D=(V,X). V={v0,v1,v2,v3,v4,v5,v6}, X={x0,x1,x2,x3,x4,x5,x6,x7,x8,x9,x10}. x0=1,v0>, x1=1,v3>, x2=1,v5>, x3=1,v2>, x4=3,v3>, x5=3,v4>, x6=3,v4>, x7=4,v5>, x8=6,v5>, x9=5,v6>, x10=2,v5>.




    1. x4 – петля, x5,x6 – кратные ребра, v0 – висячая вершина.




    1. Полустепени вершин:+(v0)=0, -(v0)=1, +(v1)=4, -(v1)=0, +(v2)=1, -(v2)=1, +(v3)=3, -(v3)=2, +(v4)=1, -(v4)=2, +(v5)=1, -(v5)=4, +(v6)=1, -(v6)=1.






    Матрица смежности




    v0

    v1

    v2

    v3

    v4

    v5

    v6

    v0

    0

    0

    0

    0

    0

    0

    0

    v1

    1

    0

    1

    1

    0

    1

    0

    v2

    0

    0

    0

    0

    0

    1

    0

    v3

    0

    0

    0

    1

    2

    0

    0

    v4

    0

    0

    0

    0

    0

    1

    0

    v5

    0

    0

    0

    0

    0

    0

    1

    v6

    0

    0

    0

    0

    0

    1

    0


    Матрица инцидентности




    x0

    x1

    x2

    x3

    х4

    х5

    х6

    х7

    x8

    x9

    x10

    v0

    -1

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    v1

    1

    1

    1

    1

    0

    0

    0

    0

    0

    0

    0

    v2

    0

    0

    0

    -1

    0

    0

    0

    0

    0

    0

    1

    v3

    0

    -1

    0

    0

    ±1

    1

    1

    0

    0

    0

    0

    v4

    0

    0

    0

    0

    0

    -1

    -1

    1

    0

    0

    0

    v5

    0

    0

    -1

    0

    0

    0

    0

    -1

    -1

    1

    -1

    v6

    0

    0

    0

    0

    0

    0

    0

    0

    1

    -1

    0


    Матрица связности:




    v0

    v1

    v2

    v3

    v4

    v5

    v6

    v0

    1

    0

    0

    0

    0

    0

    0

    v1

    0

    1

    0

    0

    0

    0

    0

    v2

    0

    0

    1

    0

    0

    0

    0

    v3

    0

    0

    0

    1

    0

    0

    0

    v4

    0

    0

    0

    0

    1

    0

    0

    v5

    0

    0

    0

    0

    0

    1

    1

    v6

    0

    0

    0

    0

    0

    1

    1


    Матрица достижимости:




    v0

    v1

    v2

    v3

    v4

    v5

    v6

    v0

    1

    0

    0

    0

    0

    0

    0

    v1

    1

    1

    1

    1

    1

    1

    1

    v2

    0

    0

    1

    0

    0

    1

    1

    v3

    0

    0

    0

    1

    1

    1

    1

    v4

    0

    0

    0

    0

    1

    1

    1

    v5

    0

    0

    0

    0

    0

    1

    1

    v6

    0

    0

    0

    0

    0

    1

    1




    1. Простой цикл: v6х8v5х9v6

    Цикл: нет

    Простая цепь : v1х3v2х10v5

    Цепь: v1х1v3х4v3х6v4

    Задание 2


    Матрица длин дуг




    v0

    v1

    v2

    v3

    v4

    v5

    v0



    3

    5



    8

    3

    v1

    3



    2

    6

    7



    v2

    5

    2





    4



    v3



    6





    5



    v4

    8

    7

    4

    5





    v5

    3
















    1. Неориентированный граф G=(V,X). V={v0,v1,v2,v3,v4,v5}, X={x0,x1,x2,x3,x4,x5,x6,x7,x8}. x0={v0,v1}, x1={v0,v5}, x2={v1,v2}, x3={v1,v4}, x4={v1,v3}, x5={v0,v2}, x6={v0,v4}, x7={v2,v4}, x8={v3,v4}.




    1. v5 – висячая вершина.




    1. (v0)=4, (v1)=4, (v2)=3, (v3)=2, (v4)=4, (v5)=1.


    http://graphonline.ru/?graph=DqpDaEgcctWYgpgl




    Матрица смежности




    v0

    v1

    v2

    v3

    v4

    v5

    v0

    0

    1

    1

    0

    1

    1

    v1

    1

    0

    1

    1

    1

    0

    v2

    1

    1

    0

    0

    1

    0

    v3

    0

    1

    0

    0

    1

    0

    v4

    1

    1

    1

    1

    0

    0

    v5

    1

    0

    0

    0

    0

    0


    Матрица инцидентности




    x0

    x1

    x2

    x3

    х4

    х5

    х6

    х7

    x8

    v0

    1

    1

    0

    0

    0

    1

    1

    0

    0

    v1

    1

    0

    1

    1

    1

    0

    0

    0

    0

    v2

    0

    0

    1

    0

    0

    1

    0

    1

    0

    v3

    0

    0

    0

    0

    0

    0

    0

    1

    1

    v4

    0

    0

    0

    1

    0

    0

    1

    1

    1

    v5

    0

    1

    0

    0

    0

    0

    0

    0

    0


    Матрица связности:




    v0

    v1

    v2

    v3

    v4

    v5

    v0

    1

    1

    1

    1

    1

    1

    v1

    1

    1

    1

    1

    1

    1

    v2

    1

    1

    1

    1

    1

    1

    v3

    1

    1

    1

    1

    1

    1

    v4

    1

    1

    1

    1

    1

    1

    v5

    1

    1

    1

    1

    1

    1


    Матрица достижимости:




    v0

    v1

    v2

    v3

    v4

    v5

    v0

    1

    1

    1

    1

    1

    1

    v1

    1

    1

    1

    1

    1

    1

    v2

    1

    1

    1

    1

    1

    1

    v3

    1

    1

    1

    1

    1

    1

    v4

    1

    1

    1

    1

    1

    1

    v5

    1

    1

    1

    1

    1

    1




    1. Простой цикл: v0х0v1х2v2х5v0

    Цикл: v4x6v0x5v2x7v4x3v1x4v3х8v4

    Простая цепь: v2х5v0х1v5

    Цепь: v0х0v1х2v2х7v4х3v1х4v3


    1. Числовые характеристики

    a) Максимальное удаление – r(v) = maxwd(v,w)

    r(v0)=2, r(v1)=2, r(v2)=2, r(v3)=3, r(v4)=2, r(v5)=3

    б) Диаметр графа d(G)=maxv,wd(v,w)

    d(G)=3

    в) Радиус графа G- r(G)=minv r(v)

    R(G)=2

    г) Центры графа-v| R(G)=r(v)

    центры графа - вершины v0, v1, v2, v4.




    Рассчитаем остовное дерево графа:


    Рассчитаем минимальное остовное дерево графа:




    1. Обход графа в глубину: v0v1v2v4v3v5.

    Обход графа в ширину. 1 ярус: v0; 2 ярус: v1,v2,v4,v5; 3 ярус: v3.

    1. Число циклов в базисе (цикломатическое число графа)

    .

    Чтобы найти базис циклов графа, к остовному дереву будем добавлять по одному ребра, которые в остовное дерево не вошли. При этом на каждом шаге будем получать один простой цикл.


    Добавим ребро x3:



    Получим цикл 1: v4x6v0x0v1x3v4.

    Добавим ребро x4:



    Получим цикл 2: v3x8v4x6v0x0v1x4v3.


    Добавим ребро x5:



    Получим цикл 3: v0x0v1x2v2x5v0.

    Добавим ребро x7:



    Получим цикл 4: v4x6v0x0v1x2v2x7v4

    Полученные циклы и образуют базис циклов графа.
    1   2   3   4   5   6   7   8


    написать администратору сайта