Спецглавы

30

2) Составим матрицу инцидентности. В данном случае матрица инцидентности – это прямоугольная матрица, число строк которой равно числу вершин, то есть m 5, а число столбцов равно числу ребер, то есть n 7 . Запишем ее элементы в общем виде:

Так как граф неориентированный, то элементы матрицы будут принимать значения или 1, или 0.

Заполняем первую строку. Выделяем вершину V1, и смотрим, каким ребрам она принадлежит (инцидентна). Вершина V1

Заполняем вторую строку. Выделяем вершину V2, и смотрим, каким ребрам она инцидентна. Вершина V2 инцидентна ребрам

31

3) Степенью вершин графа называется сумма инцидентных ей ребер.

Из вершины V1 выходит два ребра, d V1 2. Вершине V2 инцидентны три ребра, d V2 3 . Для остальных вершин: d V3 4 ,

d V4 2 , d V5 3.

4) Маршрутом в графе называется чередующаяся последовательность вершин и ребер, в которой любые два соседних элемента инцидентны. Длина маршрута равна количеству ребер в нем (с повторениями) Составим маршрут длины, равной 5:

МV1, l2 ,V3 , l3 ,V4 , l4 ,V5 ,l5 ,V2 , l6 ,V3 .

5)Составим цепь и простую цепь, соединяющие вершины V2 и V5. В цепи все ребра различны: М1 V2 , l6 ,V3 , l2 ,V1 , l1 ,V2 , l5 ,V5 .

В простой цепи все вершины (и ребра) различны:

М2 V2 , l5 ,V5 .

6)Построим простой цикл, содержащий вершину V4. Проложим через V4 замкнутый маршрут, в котором нет повторяющихся вершин и

ребер: М 3 V4 , l4 ,V5 , l5 ,V2 , l6 ,V3, l3 ,V4 .

ЗАДАНИЕ 6.

Орграф задан матрицей смежности.

1)Построить изображение этого графа;

2)указать степени его вершин;

3)записать матрицу инцидентности.

1) В орграфе четыре вершины: V1, V2 , V3 , V4 . Запишем элементы матрицы в общем виде и проанализируем их значения.

32

a11 = 0 при вершине 1 нет петель;

a12 = 2 из вершины 1 выходят две стрелки к вершине 2;

a13 = 0 из вершины 1 не выходит ни одной стрелки к вершине 3; a14 = 0 из вершины 1 не выходит ни одной стрелки к вершине 4; a21 = 0 из вершины 2 не выходит ни одной стрелки к вершине 1; a22 = 0 при вершине 2 нет петель;

a23 =1 из вершины 2 выходит одна стрелка к вершине 3;

a24 = 0 из вершины 2 не выходит ни одной стрелки к вершине 4; a31 = 1 из вершины 3 выходит одна стрелка к вершине 1;

a32 = 0 из вершины 3 не выходит ни одной стрелки к вершине 2; a33 = 0 при вершине 3 нет петель;

a34 = 1 из вершины 3 выходит одна стрелка к вершине 4; a41 = 3 из вершины 4 выходит три стрелки к вершине 1; a42 = 1 из вершины 4 выходит одна стрелка к вершине 2;

a43 = 0 – из вершины 4 не выходит ни одной стрелки к вершине 3; a44 = 0 – при вершине 4 нет петель.

Строим орграф.

33

2) Степень вершины в данном случае характеризуется двумя числами: суммой входящих ребер и суммой выходящих.

В вершину V1 входит четыре ребра, выходит два, степень V1 4, 2 . В вершину V2 входит три ребра, выходит одно, степень

V2 3,1 . Аналогично находим: V3 1, 2 , V4 1, 4 . Сумма входящих и выходящих ребер из всех вершин равна числу ребер, то есть 9.

3) Запишем матрицу инцидентности. Ее элементы могут принимать три значения: –1, 0, 1.

Заполняем первую строку, рассмотрим вершину V1. Из нее

В этой матрице количество (–1) и количество 1 одинаково, равно числу ребер, то есть 9.

ЗАДАНИЕ 2.

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

2.1. Если самолёт терпит аварию, то летчик должен либо катапультироваться, либо посадить машину.

35

2.2.Спортсмен подлежит дисквалификации, если он нетактичен по отношению к судье, или если он употребляет стимулирующие вещества.

2.3.Если студент имеет хорошее пространственное воображение, то он хорошо понимает начертательную геометрию и математику.

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

2.5.Ни извиняющийся тон, ни упорство не украшают споры.

2.6.Лишь тот достоин жизни и свободы, кто каждый день идёт за них на бой.

2.7.Плоскость касательна к сфере тогда и только тогда, когда она перпендикудярна к диаметру сферы и проходит через его конец.

2.8.Или бури завываньем ты мой друг утомлена, или дремлешь под жужжаньем своего веретена.

2.9.Для того, чтобы два ненулевых вектора были перпендикулярны, необходимо и достаточно, чтобы их скалярное произведение было равно нулю.

2.10.Кабы молодость да знала, кабы старость да могла, жизнь бы иначе пошла.

ЗАДАНИЕ 3.

Считая, что каждое из данных сложных высказываний истинное, определите значения входящих в них простых высказываний.

3.1.Андрей хорошо играет в теннис или волейбол. Неверно, что он хорошо играет в баскетбол или теннис.

3.2.Я видел фильмы по романам ™Анна Каренина® и ™Война и мир®. Неверно, что если я видел фильм по роману ™Война и мир®; то я не захочу прочитать сам роман.

3.3.Если на этой неделе будет лекция по экономике, то на следующей будет практика. Неверно, что если на этой неделе будет лекция по экономике, то на следующей не будет бухгалтерского учета.

3.4.Неверно, что эта повесть напечатана в ™Новом мире® или в ™Знамени®. Она напечатана в ™Неве® или в ™Знамени®.

3.5.Если мы пойдем на речку, то будем купаться. Неверно, что если мы будем купаться, мы не будем загорать.

36

3.6 Марина хорошо шьет или вяжет. Неверно, что она хорошо владеет макраме или вяжет.

3.7.Завтра я пойду в читальный зал и в театр. Неверно, что если я пойду в театр, я не встречусь с друзьями.

3.8.Сегодня я буду слушать музыку и делать уборку комнаты. Неверно, что если я буду делать уборку комнаты, то не успею приготовить обед.

3.9.Неверно, что Борис занимается бегом или плаванием. Он занимается теннисом или плаванием.

3.10.В сессию он ходит в библиотеку и читает много книг. Неверно, что если он читает много книг, то у него болит голова.

ЗАДАНИЕ 4.

Установите, являются ли равносильными следующие суждения.

4.1.Если студент сдал все зачеты, то он допущен к экзаменам. Если студент допущен к экзаменам, значит он сдал все зачеты.

4.2.Если студент сдал все зачеты, то он допущен к экзаменам. Если студент не допущен к экзаменам, то он не сдал все зачеты.

4.3.Если студент не допущен к экзаменам, значит он не сдал зачеты. Если студент не сдал зачеты, то он не допущен к экзаменам.

4.4.Неверно, что лекция по математике будет в понедельник или вторник. В понедельник и вторник лекции по математике не будет.

4.5.Неверно, что лекция по математике будет в понедельник или вторник. В понедельник или вторник лекции по математике не будет.

4.6.Эту книгу очень хвалят, но я ее не читала. Неверно, что если эту книгу очень хвалят, то я ее читала.

4.7.Неверно, что Галя и Света пошли в кино. Галя не пошла в кино и Света не пошла в кино.

4.8.На вечере в студклубе будут танцы и выступление ансамбля или будет концерт и танцы. На вечере в студклубе будут танцы, и еще будет концерт или выступление ансамбля.

4.9.Неверно, что автобусы № 29 или № 27 идут до аэропорта. Автобусы № 29 и 27 не идут до аэропорта.

37

4.10. Если Сергей сможет купить билет, то в субботу он поедет домой. Если в субботу Сергей поедет домой, значит, он смог купить билет.

ЗАДАНИЕ 5.

Граф G задан диаграммой. Для него:

1)составить матрицу смежности;

2)составить матрицу инцидентности;

3)указать степени вершин графа;

4)составить маршруты длины, равной 5;

5)составить цепь и простую цепь, соединяющие вершины V2 и V5;

6)построить простой цикл, содержащий вершину V4.

V1