Студопедия — Задание 4. Формула называется выполнимой, если существует такой набор высказываний, который обращает эту формулу в истинное высказывание (есть хотя бы одно значение 1 в
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Задание 4. Формула называется выполнимой, если существует такой набор высказываний, который обращает эту формулу в истинное высказывание (есть хотя бы одно значение 1 в

Задание 4

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

Граф, состоящий из дуг, называют ориентированным (орграфом), а образованный ребрами — неориентированным.

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

Формально граф определяется заданием двух множеств и , где — множество вершин; — множество дуг (ребер).

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

Матрица смежности вершин орграфа — это квадратная матрица -го порядка ( — число вершин). Строки и столбцы матрицы соответствуют вершинам графа. Элементы матрицы равны числу дуг, направленных из -й вершины в -ю. Если орграф состоит из однократных дуг, то элементы матрицы равны либо 0, либо 1. Если орграф состоит из однократных дуг, то элементы матрицы равны либо 0, либо 1.

В случае неориентированного графа ему вместе с ребром принадлежит и ребро , поэтому матрица будет симметрической. Справедливо и обратное заключение: любой симметрической матрице с целыми неотрицательными элементами можно поставить в соответствие граф.

Матрица смежности дуг орграфа — это квадратная матрица -го порядка ( — число дуг). Строки и столбцы матрицы соответствуют дугам графа. Элементы равны 1, если дуга непосредственно предшествует дуге , и 0 в остальных случаях.

Матрицей смежности ребер неориентированного графа является матрица -го порядка ( — число ребер) с элементами равными 1, если ребра и имеют общую вершину, и 0 в остальных случаях.

Матрица инцидентности орграфа — это прямоугольная матрица размерности , строки которой соответствуют вершинам, а столбцы — дугам орграфа. Элементы равны 1, если дуга исходит из -й вершины; , если дуга заходит в -ю вершину; 0, если дуга не инцидентна -й вершине. В случае неориентированного графа элементами матрицы будут лишь 1 и 0.

 

Пример.




<== предыдущая лекция | следующая лекция ==>
Классификация формул алгебры высказываний | Сводную ведомость (вариационный ряд) информации по износам представим в виде таблицы 3, в которой полученные расчётом износы расположены в порядке их возрастания

Дата добавления: 2015-03-11; просмотров: 486. Нарушение авторских прав; Мы поможем в написании вашей работы!



Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...

Важнейшие способы обработки и анализа рядов динамики Не во всех случаях эмпирические данные рядов динамики позволяют определить тенденцию изменения явления во времени...

ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...

Теория усилителей. Схема Основная масса современных аналоговых и аналого-цифровых электронных устройств выполняется на специализированных микросхемах...

Примеры решения типовых задач. Пример 1.Степень диссоциации уксусной кислоты в 0,1 М растворе равна 1,32∙10-2   Пример 1.Степень диссоциации уксусной кислоты в 0,1 М растворе равна 1,32∙10-2. Найдите константу диссоциации кислоты и значение рК. Решение. Подставим данные задачи в уравнение закона разбавления К = a2См/(1 –a) =...

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

В теории государства и права выделяют два пути возникновения государства: восточный и западный Восточный путь возникновения государства представляет собой плавный переход, перерастание первобытного общества в государство...

Типовые ситуационные задачи. Задача 1. Больной К., 38 лет, шахтер по профессии, во время планового медицинского осмотра предъявил жалобы на появление одышки при значительной физической   Задача 1. Больной К., 38 лет, шахтер по профессии, во время планового медицинского осмотра предъявил жалобы на появление одышки при значительной физической нагрузке. Из медицинской книжки установлено, что он страдает врожденным пороком сердца....

Типовые ситуационные задачи. Задача 1.У больного А., 20 лет, с детства отмечается повышенное АД, уровень которого в настоящее время составляет 180-200/110-120 мм рт Задача 1.У больного А., 20 лет, с детства отмечается повышенное АД, уровень которого в настоящее время составляет 180-200/110-120 мм рт. ст. Влияние психоэмоциональных факторов отсутствует. Колебаний АД практически нет. Головной боли нет. Нормализовать...

Эндоскопическая диагностика язвенной болезни желудка, гастрита, опухоли Хронический гастрит - понятие клинико-анатомическое, характеризующееся определенными патоморфологическими изменениями слизистой оболочки желудка - неспецифическим воспалительным процессом...

Studopedia.info - Студопедия - 2014-2024 год . (0.012 сек.) русская версия | украинская версия