7.10. Задачи для самостоятельного решения
Какое из двух утверждений верно?
а) ориентированный граф является частным случаем неориентированного графа;
б) неориентированный граф является частным случаем ориентированного графа.
Что характеризует сумма элементов столбца матрицы смежности неориентированного графа?
Что характеризует сумма элементов строки матрицы смежности неориентированного графа?
Что характеризует сумма элементов столбца матрицы смежности ориентированного графа?
Что характеризует сумма элементов строки матрицы смежности ориентированного графа?
Всегда ли матрица смежности симметрична относительно главной диагонали?
Как по матрице смежности определить число ребер неориентированного графа?
Как по матрице инцидентности, не рисуя граф, определить его матрицу смежности?
Какие из следующих утверждений являются правильными?
а) если матрица смежности несимметричная, то граф ориентированный;
б) если граф неориентированный, то матрица смежности симметричная;
в) если диагональные элементы матрицы смежности – нули, то граф неориентированный.
Может ли вершина, входящая в цикл графа, иметь степень, меньшую двух?
Как называется путь, у которого начало первой дуги совпадает с концом последней?
Как называется маршрут, у которого первая вершина совпадает с последней вершиной?
Какие из следующих матриц полностью задают граф?
а) матрица инцидентности; б) матрица связности;
в) матрица сильной связности; г) матрица смежности.
По какой матрице можно без дополнительных вычислений определить число компонент связности неориентированного графа?
а) матрице смежности; б) матрице инцидентности;
в) матрице связности.
Может ли число компонент связности графа превосходить число его вершин?
Верно или неверно утверждение, что в ориентированном графе с контурами минимальный путь может содержать контуры?
Как называется связный граф без циклов?
Сколько ребер имеет связный граф без циклов с вершинами?
Чему равно наименьшее и наибольшее число ребер в связном графе без петель и кратных ребер с вершинами?
Чему равно наименьшее и наибольшее число ребер в графе без петель и кратных ребер с вершинами?
Верно или неверно утверждение, что минимальное остовное дерево может содержать циклы?
Сколько компонент связности может иметь дерево?
Можно ли построить дерево, все вершины которого имеют степень больше, чем единица?
Может ли матрица
быть матрицей смежности неориентированного
графа?
Литература
Хаусдорф Ф. Теория множеств. – 3-е изд., стер. – М.: КомКнига, 2006.
Москинова Г. И. Дискретная математика. Математика для менеджера в примерах и упражнениях. – М.: Логос, 2007.
Аляев Ю. А., Тюрин С. Ф. Дискретная математика и математическая логика: учебник. – М.: ФиС, 2006.
Оре О. Графы и их применение. – 3-е изд., стер. – М.: КомКнига, 2006.
Лавров И. А., Максимова Л. Л. Задачи по теории множеств, математической логике и теории алгоритмов. – М.: Физматлит, 2001, 2004.
Обработка нечеткой информации в системах принятия решения / А. Н. Борисов, А. В. Алексеев, Г. В. Меркулова и др. – М.: Радио и связь, 1989.
Кирсанов М. Н. Графы в Maple. Задачи, алгоритмы, программы. (Сер. «Информационные и компьютерные технологии»). – М.: Физматлит, 2007.
Кофман А. Введение в теорию нечетких множеств. – М.: Радио и связь, 1982.
Андерсон Дж. А. Дискретная математика и комбинаторика. – М.: Вильямс, 2004.
Кузнецов О. П. Дискретная математика для инженера. – 6 изд. СПб.: Лань, 2009.
Палий И. А. Дискретная математика: курс лекций. – М.: Эксмо, 2008.
Хаггарти Р. Дискретная математика для программистов. – М.: Техносфера, 2005.
Шапорев С. Д. Дискретная математика: курс лекций и практических занятий. – СПб.: БХВ-Петербург, 2007.
Яблонский С. В. Введение в дискретную математику. 4-е изд., стер. – М.: Высшая школа, 2003.
Поздняков С. Н., Рыбин С. В. Дискретная математика: учебник для вузов. 2-е изд., перераб. и допол. – М.: Академия, 2008.
Плотников А. Д. Дискретная математика. – 3-е изд., исп. и доп. – Минск: Новое знание, 2008.
Акимов О. Е. Дискретная математика: логика, группы, графы. – М.: Лаборатория Базовых Знаний, 2001.
Липский В. Комбинаторика для программистов. – М.: Мир, 1988.
Нефедов В. Н., Осипова В. А. Курс дискретной математики. – М.: Изд. – МАИ, 1992.
Новиков Ф. А. Дискретная математика для программистов. Учебник для вузов. 2-е изд.– СПб.: Питер, 2007.
Судоплатов С. В., Овчинникова В. В. Элементы дискретной математики. – М.: ИНФРА – М, Новосибирск: Изд-во НГТУ, 2002.
Иванов Б. И. Дискретная математика. – М., Физматлит, 2007.
Иванов Б. Н. Дискретная математика. Алгоритмы и программы: Учеб. пособие. (Сер. «Технический университет»). – М.: Лаборатория Базовых Знаний, 2003.
24. Тишин В. В. Дискретная математика в примерах и задачах. (Учебная литература для вузов). – СПб.: БХВ-Петербург, 2008.