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


  • Введение в теорию графов

  • Основные определения

  • Определение.

  • О пределение.

  • Доказательство.

  • Определение.

  • Изоморфизм графов.

  • Достижимость и связность

  • Учебник по дискретной математики. Д. Ушинского Дискретная математика


    Скачать 2.66 Mb.
    НазваниеД. Ушинского Дискретная математика
    АнкорУчебник по дискретной математики.doc
    Дата20.05.2017
    Размер2.66 Mb.
    Формат файлаdoc
    Имя файлаУчебник по дискретной математики.doc
    ТипДокументы
    #8001
    страница11 из 20
    1   ...   7   8   9   10   11   12   13   14   ...   20

    Бином Ньютона. Полиномиальная формула.


    1. Раскрыть скобки: (а+в) 5, (3х+2у)6.

    2. Найти коэффициент при х7 в выражении (2х+3)12.

    3. Найти коэффициент при х10 в выражении (3х-2)13.

    4. В выражении (x+2y)10 раскрыли скобки и привели подобные члены. Какой коэффициент будет стоять при выражения x4y6.

    5. Доказать с помощью треугольника Паскаля:

    1. Чему равна сумма?

    2. Чему равна сумма ?

    3. Докажите тождество .

    4. Докажите тождество .

    5. Получить все различные коэффициенты, которые будут появляться при приведении подобных членов в формулах: (x+y+z)6 и (x+y+z+u)5.

    6. Найти коэффициенты при х7 после раскрытия скобок и приведения подобных членов в выражении (2+х34)13.

    7. Найти коэффициенты при х8 после раскрытия скобок и приведения подобных членов в выражении (1+х23)9.

    8. Найти коэффициенты при х17 и х18 после раскрытия скобок и приведения подобных членов в выражении (1+х57)20.

    9. В каком из выражений (1+х23)1000, (1-х23)1000 будет после раскрытия скобок и приведения подобных членов больший коэффициент при х17.

    Рекуррентные соотношения.


    1. Подсчитать количество последовательностей длины N, состоящих из 0 и 1, в которых никакие две единицы не стоят рядом.

    2. Посылка бандероли стоит 18 рублей, а на почте имеются марки по 4, 6 и 10 рублей. Сколькими разными способами можно наклеить на бандероль марки, на нужную сумму?

    3. Имеется возможность передавать 4 разных сигнала А, Б, В, Г, причем их передача занимает соответственно Т1, Т2 Т3, Т4 (целые) единиц времени. Сколько различных сообщений может быть передано за время Т (тоже целое)?

    4. Абитуриент сдает в вуз 4 экзамена по 5-балльной системе и хочет набрать не менее 17 баллов. Сколькими способами он может это сделать.

    5. Сколькими способами можно разбить натуральное число М на К простых слагаемых, где способы разбиения, отличающиеся порядком слагаемых, считаются разными? Например при М=10 и К=2 ответом будет 3, так как 10=3+7=5+5=7+3.

    6. В лототроне имеются бочонки с номерами от 1 до К. Последовательно вынимают по одному бочонку, записывают его номер и считают сумму записанных чисел. Сколькими способами может получиться сумма М?

    7. В лототроне имеются бочонки с номерами от 1 до К. Последовательно вынимают по одному бочонку, записывают его номер и считают сумму записанных чисел, после записывания номера бочонок возвращается обратно в лототрон. Сколькими способами может получиться сумма М?

    8. На единственной улице в деревне стоят К домов с известными координатами. Требуется соединить их телефонными проводами минимальной суммарной длины так, чтобы житель каждого дома мог пообщаться хотя бы с одним жителем другого дома.

    9. В пригородном автобусе кондуктор следил за тем, чтобы все покупали билеты и отмечал, сколько билетов (ki,j) куплено с i–й остановки до j–й. По известной матрице ki,j нужно найти промежуток времени, когда в автобусе было максимальное количество пассажиров и чему оно равно.

    10. Прямоугольная таблица размерами МхК произвольно заполнена цифрами от 0 до 9. Найти путь из левого нижнего угла в правый верхний с максимальной суммой цифр в клетках пути (разрешается на каждом шаге переходить вверх или вправо).

    11. В романе N глав, причем р-я глава состоит из Ар страниц. Роман нужно разбить на К томов, причем главы должны идти по порядку и главы нельзя разбивать в разные тома. Какова может быть минимальная толщина самого толстого тома при этом?

    12. Для последовательности с f(1)=5 и f(2)=13, удовлетворяющей рекуррентному соотношению f(к+2)=5f(к+1)-6f(к), выписать формулу общего члена.

    13. Для последовательности с f(0)=6 и f(1)=24, удовлетворяющей рекуррентному соотношению f(к+2)=6f(к+1)-9f(к), выписать формулу общего члена.

    14. Для последовательности с f(0)=4, f(1)=-7 и f(2)=15, удовлетворяющей рекуррентному соотношению f(к+3)=-6f(к+2)-11f(k+1)-6f(к), выписать формулу общего члена.

    15. Найдите общее решение рекуррентных соотношений:

    a) аn+2-7an+1+12an=0;

    b) аn+2+3an+1-10an=0;

    c) аn+2+9an=0 ;

    d) аn+2+4an+1+4an=0.

    1. Найдите решение рекуррентного соотношения:

    1. аn+2-5an+1+6an=0, а1=1, а2=-7;

    2. аn+2-4an+1+4an=0, а1=2, а2=4.

    Введение в теорию графов

    Среди дисциплин и методов дискретной математики теория графов и особенно алгоритмы на графах находят наиболее широкое применение в программировании. Дело в том, что теория графов дает очень удобный язык для описания программных моделей. Особенно важно наличие наглядной графической интерпретации понятия графа. Картинки позволяют сразу «усмотреть» суть дела на интуитивном уровне, дополняя и украшая утомительные рациональные текстовые доказательства и сложные формулы.

    Начало теории графов относят к 1736 г., когда Л. Эйлер решил задачу о Кениксбергских мостах. Около 100 лет это был единственный результат теории графов. В задаче о Кениксбергских мостах (см. рис. 1) необходимо было определить можно ли, начав с некоторой точки, совершить прогулку и вернуться в исходную точку, пройдя по каждому мосту ровно один раз.



    В 1930 году К. Куратовским была решена задача о трех домах и трех колодцах, сформулированная следующим образом: «Имеются три дома и три колодца. Жители домов поссорились и решили проложить дороги к своим колодцам так, чтобы они не пересекались. Возможно ли это?»

    Почти 100 лет не была доказана теорема о раскраске карты: «Любую карту на плоскости можно раскрасить четырьмя красками так, чтобы никакие две соседние области не были закрашены одним цветом.»

    Родившись при решении головоломок и занимательных игр, теория графов стала в настоящее время простым, доступным и мощным средством решения вопросов, относящихся к широкому кругу проблем. В виде графов можно интерпретировать схемы дорог и электрические цепи, географические карты и молекулы химических соединений, связи между людьми и группами людей. То есть виде графа можно изобразить любую структуру, на которой задано некоторое отношение между её объектами.

    На рисунках 2 и 3 изображены участок электрической цепи и часть карты дорог. Ясно, что оба эти рисунка могут быть представлены одной и той же диаграммой из точек и линий, изображенной на рисунке 4






    Основные определения

    Определение. Определим граф как совокупность двух множеств непустого множества V (множество вершин) и множества E неупорядоченных и упорядоченных пар вершин из V.

    Определение. Неупорядоченная пара вершин называется ребром, а упорядоченная пара - дугой.

    Определение. Граф, содержащий только ребра, называется неориентированным; граф, содержащий только дуги, - ориентированным, или орграфом, содержащий и ребра и дуги – смешанным.

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

    На рисунке 5 изображен неориентированный граф G1, с пятью вершинами и восьмью ребрами.

    На рисунках 6 и 7 изображены ориентированный и смешанный графы, соответственно.



    Обозначения

    Множество вершин будем обозначать большой латинской буквой V. Элементы этого множества (вершины) – маленькими латинскими буквами v с индексом. Множество ребер (дуг) обозначим большой латинской буквой Е, а сами ребра (дуги) - маленькими латинскими буквами е с индексом. Граф G с множеством вершин V и множеством ребер Е будем обозначать G(V,E). Количество вершин (мощность множества V) будем обозначать |V|, количество ребер (дуг) – |E|.

    Для графа, изображенного на рисунке 1.5

    V={v1, v2, v3, v4, v5, }, |V|=5,

    E={e1, e2, e3, e4, e5, e6, e7, e8}, |E|=8.

    Определение. Вершины, соединенные ребром (дугой), называются смежными. Ребра (дуги), имеющие общую вершину, также называются смежными.

    Определение. Ребро и любая из его двух вершин называются инцидентными.

    Определение. Степень вершины в неориентированном графе - число ребер, концом которых является эта вершина. Будем обозначать степень i-той вершины через deg vi.

    Например, для графа, изображенного на рисунке 5:

    • вершины v1 и v2смежны, а вершины v4 и v2не смежны.

    • ребро е1 инцидентно вершинам v1 и v2

    • степень первой вершины равна 4 (deg v1=4).

    Определение. Пусть v вершина орграфа D назовем полустепенью исхода v число дуг орграфа D, имеющих вид (v, w); аналогично полустепенью захода v назовем число дуг вида (w, v).

    Будем обозначать полустепень захода i-той вершины через deg+ vi, полустепень исхода i-той вершины через deg- vi.

    Например, для графа, изображенного на рисунке 6 deg+ v1=3, deg- v1=1.

    Определение. Если два ребра инцидентны одной и той же паре вершин, они называются кратными.

    Определение. Граф, содержащий кратные ребра называется мультиграфом..

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



    Определение. Ребро (дуга) называется петлей, если начало и конец его (её) совпадают.

    О
    пределение.
    Граф содержащий петли называется псевдографом


    Рис. 9


    На рисунке 9 изображен мульти-псевдограф.
    Определение. Неориентированный граф без петель и кратных ребер называется простым графом.

    Теорема. (Лемма о рукопожатиях). В простом графе сумма степеней всех его вершин – число четное, равное удвоенному числу ребер графа.

    Доказательство. Очевидно, что каждое ребро вносит 2 в сумму степеней вершин.

    Теорема. Число нечетных вершин простого графа четно.

    Доказательство. Предположим противное: существует граф G, имеющий нечетное количество вершин нечетной степени. Подсчитаем сумму степеней всех вершин – она будет нечетной, что противоречит лемме о рукопожатиях.

    Орлемма о рукопожатии. Сумма полустепеней захода всех вершин орграфа равна сумме полустепеней исхода всех вершин.



    Доказательство. Каждая дуга “участвует” в каждой сумме ровно один раз.

    Примеры графов

    Определение. Регулярный граф – граф, у которого все вершины имеют одну и ту же степень.



    На рисунке 10 изображен регулярный граф со степенью регулярности 2. На рисунке 11 – регулярный граф со степенью регулярности 3. Граф, изображенный на рисунке 11 называют графом Петерсона, он интересен тем, что любые две его вершины соединены маршрутом, проходящим не более чем по двум ребрам.
    Определение. Граф называется полным, если каждые две его различные вершины соединены одним и только одним ребром.

    Полный граф с n вершинами обозначается Кn. На рисунке 12 изображены полные графы на 2, 3 и 5 вершинах.




    Определение. Двудольный граф-это граф G(V,E), такой что множество V разбито на два непересекающихся множества V1 и V2(, ), причем всякое ребро из E соединяет вершину из V1 с вершиной из V2. Множества V1 и V2 называются долями двудольного графа. Если двудольный граф содержит все ребра, соединяющий множества V1 и V2, то он называется полным двудольным графом.

    Полный двудольный граф с m вершинами в одной доле и n вершинами в другой обозначается Кmn. На рисунке 13 изображен полный двудольный граф К33



    Способы описания графа.

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

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


    1. Матрица смежности - это двумерный массив размерности N*N.

    Для неориентированного графа

    A[i,j]=

    Для неориентированного графа - это симметричная матрица с нулями на главной диагонали. Сумма цифр в любой строке или столбце равна степени соответствующей вершины.

    Ниже представлена матрица смежности графа, изображенного на рисунке 13



    Для ориентированных графов

    1, существует дуга (i, j)

    A[i,j]=

    0, не существует дуги вида (i, j)
    Для ориентированных графов матрица смежности не будет симметрична относительно главной диагонали. Для ориентированных мульти- и псевдографов A[i,j] равно количеству дуг, соединяющих вершину i с вершиной j.

    На рисунке 14 изображен ориентированный мульти-псевдограф и его матрица смежности


    Матрица инциденций


    Матрица инциденций отражает инцидентность вершин и ребер.

    Для неориентированных графов

    1, вершина с номером i инцидентна ребру с номером j,

    A[i,j]=

    0, вершина с номером i не инцидентна ребру с номером j.

    На рисунке 15 изображен простой граф и его матрица инцидентности.



    Для ориентированных графов

    1, вершина с номером i инцидентна ребру с номером j и является его концом,

    A[i,j]= 0, вершина с номером i не инцидентна ребру с номером j,

    -1 вершина с номером i инцидентна ребру с номером j и является его началом.

    На рисунке 16 изображен орграф и его матрица инцидентности.






    1

    2

    3

    4

    5

    6

    7

    8

    1

    -1

    0

    0

    0

    1

    0

    1

    1

    2

    1

    1

    0

    0

    0

    1

    0

    0

    3

    0

    -1

    1

    0

    0

    0

    0

    -1

    4

    0

    0

    -1

    1

    0

    0

    -1

    0

    5

    0

    0

    0

    -1

    -1

    -1

    0

    0



    Перечень ребер


    Для хранения перечня ребер используют двумерный массив размерности |Е| х 2, каждая строка которого описывает ребро графа.

    Для графа, изображенного на рисунке 15 перечень ребер имеет вид:

    1

    2

    3

    4

    1

    2

    1

    1

    2

    3

    4

    5

    5

    5

    4

    3

    Изоморфизм графов.

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

    На рисунке 17 изображены изоморфные графы.


    Достижимость и связность

    Определение. Маршрут – это последовательность ребер (дуг) графа, в которой конец каждого ребра (дуги) совпадает с началом следующего ребра.


    Определение. Число ребер маршрута называется его длиной.

    Определение. Циклом называется замкнутый маршрут.

    Например, в графе, изображенном на рисунке 18, вершины v5иv3 соединены маршрутами 6, е2) длины 2; (е5, е1, е2) длины 3. Маршрут 5, е1, е2, е3, е4) является циклом.

    Определение. Если существует маршрут из вершины графа v в вершину u, то говорят, что u достижима из v.
    1   ...   7   8   9   10   11   12   13   14   ...   20


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