Граф и график соответствия. Соответствие, обратное данному. Виды соответствий
Понятие соответствия. Способы задания соответствий
СООТВЕТСТВИЯ МЕЖДУ ДВУМЯ МНОЖЕСТВАМИ
Лекция 16. Соответствия
1. Понятие соответствия. Способы задания соответствий.
2. Граф и график соответствия. Соответствие, обратное данному. Виды соответствий.
3. Взаимно-однозначные соответствия
Первоначально алгеброй называли учение о решении уравнений. За много столетий своего развития алгебра превратилась в науку, которая изучает операции и отношения на различных множествах. Поэтому не случайно уже в начальной школе дети знакомятся с такими алгебраическими понятиями, как выражение (числовое и с переменными), числовое равенство, числовое неравенство, уравнение. Они изучают различные свойства арифметических действий над числами, которые позволяют рационально выполнять вычисления. И конечно, в начальном курсе математики происходит их знакомство с различными зависимостями, отношениями, но чтобы использовать их в целях развития мыслительной деятельности детей, учитель должен овладеть некоторыми общими понятиями современной алгебры — понятием соответствия, отношения, алгебраической операции и др. Кроме того, усваивая математический язык, используемый в алгебре, учитель сможет глубже понять сущность математического моделирования реальных явлений и процессов.
Изучая окружающий нас мир, математика рассматривает не только его объекты, но и главным образом связи между ними. Эти связи называют зависимостями, соответствиями, отношениями, функциями. Например, при вычислении длин предметов устанавливаются соответствия между предметами и числами, которые являются значениями их длин; при решении задач на движение устанавливается зависимость между пройденным расстоянием и временем, если скорость движения постоянна.
Конкретные зависимости, соответствия, отношения между объектами в математике изучались с момента ее возникновения. Но вопрос о том, что общее имеют самые разные соответствия, какова сущность любого соответствия, был поставлен в конце XIX — начале XX века, и ответ на него был найден в рамках теории множеств.
В начальном курсе математики изучаются различные взаимосвязи между элементами одного, двух и более множеств. Поэтому учителю надо понимать их суть, что поможет ему обеспечить единство в методике изучения этих взаимосвязей.
Рассмотрим три примера соответствий, изучаемых в начальном курсе математики.
| I. Найти значение выражения: | II.Найти площадь фигуры | III. Решить уравнение: |
| в1) (17-1):4; в2) (12 + 18) : (6-6); в3) 2·7 + 6. | y1) 2 + x = 6; y2) x – 7 = 4; y3) 2x = 8 |
В первом случае мы устанавливаем соответствие между заданными выражениями и их числовыми значениями. Во втором выясняем, какое число соответствует каждой из данных фигур, характеризуя ее площадь. В третьем ищем число, которое является решением уравнения.
Что общее имеют эти соответствия?
Видим, что во всех случаях мы имеем два множества: в первом -это множество из трех числовых выражений и множество N натуральных чисел (ему принадлежат значения данных выражений); во втором -это множество из трех геометрических фигур и множество N натуральных чисел; в третьем — это множество из трех уравнений и множество N натуральных чисел.
Выполняя предложенные задания, мы устанавливаем связь (соответствие) между этими множествами. Ее можно представить наглядно, при помощи графов (рис. 67).
Можно задать эти соответствия, перечислив все пары элементов, плодящихся в заданном соответствии:
Рис. 67
Полученные множества показывают, что любое соответствие между двумя множествами X и Y можно рассматривать как множество упорядоченных пар, образованных из их элементов. А так как упорядоченные пары — это элементы декартова произведения, то приходим к следующему определению общего понятия соответствия.
Определение.Соответствием между множествами X и Y называется всякое подмножество декартова произведения этих множеств.
Соответствия принято обозначать буквами Р, S, Т, К и др. Если S -соответствие между элементами множеств X и Y то, согласно определению, S с Х х У.
Выясним теперь, как задают соответствия между двумя множествами. Поскольку соответствие — это подмножество, то его можно задавать как любое множество, т.е. либо перечислив все пары элементов, находящихся в заданном соответствии, либо указав характеристическое свойство элементов этого подмножества. Так, соответствие между множествами X — <1, 2, 4, 6>и У = <3, 5>можно задать:
1) при помощи предложения с двумя переменными: а -1 , то S -1 = <(2,4), (3,5), (6,8)>.
 |
Рис.70 
Условимся предложение «элемент х находится в соответствии S с элементом у» записывать кратко так: хSу. Запись хSу можно рассматривать как обобщение записей конкретных соответствий: x= 2у; х > 3у+1 и др.
Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет
Источник
Графы и способы их представления
Способы описания графов
Теоретико-множественное представление графов
Граф описывается перечислением множества вершин и дуг. Примеры описания приведены для орграфов на рис. 1.3 и рис. 1.4.
где X =
Задание графов соответствием
Описание графов состоит в задании множества вершин Х и соответствия Г , которое показывает, как между собой связаны вершины.
Соответствием Г называется отображение множества Х в Х , а граф в этом случае обозначается парой G = (X, Г) .
Отображением вершины хi — Г(хi) является множество вершин, в которые существуют дуги из вершины хi , т. е. 
.
Так для орграфа на рис. 1.3 описание заданием множества вершин и соответствия выглядит следующим образом:
Для неориентированного или смешанного графов предполагается, что соответствие Г задает такой эквивалентный ориентированный граф , который получается из исходного графа заменой каждого неориентированного ребра двумя противоположно направленными дугами, соединяющими те же самые вершины. Например, для графа на рис. 1.2,б Г(х2) = < х1, х3, х5 >, Г(х4) =< х3, х5> и т. д.
Матричное представление графов
Для обработки на ЭВМ графы удобно представлять в виде матриц смежности и инциденций .
Матрица смежности – это квадратная матрица размерностью n x n , (где n – число вершин графа ), однозначно представляющая его структуру.
A =
aij = 1 , если 
дуга (хi, хj) ,
Если элемент на диагонали (i=j) равен единице, значит, вершина i имеет петлю.
Матрица инциденций представляет собой прямоугольную матрицу размером n x m , где n – количество вершин графа , а m – количество дуг графа . Обозначается матрица инциденций B =
Каждый элемент матрицы определяется следующим образом:
bij = 1 , если хi является начальной вершиной дуги aj ,
bij = –1 , если хi является конечной вершиной дуги aj ,
bij = 0 , если хi не является концевой вершиной дуги aj или если aj является петлей.
Таким образом, нулевой столбец j в матрице инциденций свидетельствует о том, что дуга aj яляется петлей.
На рис. 1.5, а,б приведен граф и его матрица смежности , по которой можно найти характеристики вершин. Так сумма элементов i -ой строки матрицы дает полустепень исхода вершины хi , а сумма элементов i -го столбца дает полустепень захода вершины хi . По матрице смежности можно найти прямые и обратные отображения. Рассмотрим i -ю строку матрицы. Если элемент aij=1 , то элемент графа хj входит в отображение Г(хi) . Например, во 2-й строке матрицы А ( рис. 1.5,б) единицы стоят в 2-м и 5-м столбцах, следовательно, Г(х2) = < х2, х5> .
Для графа на рис. 1.5,а матрица инциденций приведена на рис. 1.5,в. Поскольку каждая дуга инцидентна двум различным вершинам, за исключением того случая, когда дуга образует петлю, то каждый столбец либо содержит один элемент равный 1 и один – равный – 1, либо все элементы столбца равны 0.
Для неориентированного графа , матрица инциденций определяется так же, за исключением того, что все элементы, равные –1, заменяются на 1.
Источник
2. Граф и график соответствия. Соответствие, обратное данному. Виды соответствий.
Выполняя предложенные задания, мы устанавливаем связь (соответствие) между этими множествами. Ее можно представить наглядно, при помощи графов (рис. 67).
Можно задать эти соответствия, перечислив все пары элементов, плодящихся в заданном соответствии:
Полученные множества показывают, что любое соответствие между двумя множествами X и Y можно рассматривать как множество упорядоченных пар, образованных из их элементов. А так как упорядоченные пары — это элементы декартова произведения, то приходим к следующему определению общего понятия соответствия.
Определение. Соответствием между множествами X и Y называется всякое подмножество декартова произведения этих множеств.
Соответствия принято обозначать буквами Р, S, Т, К и др. ЕслиS-соответствие между элементами множествX иYто, согласно определению,S с Х х У.
Выясним теперь, как задают соответствия между двумя множествами. Поскольку соответствие — это подмножество, то его можно задавать как любое множество, т.е. либо перечислив все пары элементов, находящихся в заданном соответствии, либоуказав характеристическое свойство элементов этого подмножества. Так, соответствие между множествамиX — <1, 2, 4, 6>иУ = <3, 5>можно задать:
при помощи предложения с двумя переменными: а -1 , то S -1 = <(2,4), (3,5), (6,8)>.
Рис.70 
Условимся предложение «элемент х находится в соответствии S с элементом у» записывать кратко так: хSу. Запись хSу можно рассматривать как обобщение записей конкретных соответствий: x= 2у; х > 3у+1 и др.
3. Взаимно-однозначные соответствия
Воспользуемся введенной записью для определения понятия соответствия, обратного данному.
Соответствия S и S -1 называют взаимно обратными. Выясним особенности их графиков.
Построим график соответствия S = <(4, 2), (5, 3), (8, 6)>(рис. 71, а). При построении графика соответствия S -1 = <(2, 4), (3, 5), (6, 8)>мы должны первую компоненту выбирать из множества Y = <2, 3, 6>, а вторую — из множества Х= <4, 5, 8, 10>. В результате график соответствия S -1 совпадет с графиком соответствия S. Чтобы различать графики соответствий S и S -1 , условились первую компоненту пары соответствия S -1 считать абсциссой, а вторую — ординатой. Например, если (5, 3) € S, то (3, 5) € S -1 . Точки с координатами (5, 3) и (3, 5), а в общем случае (х,у) и (у, х) симметричны относительно биссектрисы 1-го и 3-го координатных углов. Следовательно, графики взаимно обратных соответствий S и S -1 симметричны относительно биссектрисы 1-го и 3-го координатных углов.
Чтобы построить график соответствия S -1 , достаточно изобразить на координатной плоскости точки, симметричные точкам графикаSотносительно биссектрисы 1-го и 3-го координатных углов.
Источник
Способы задания графов.
Рассмотрим три способа задания графов: графический, аналитический и матричный.
1) Графический способ.
Вершины изображают точками на плоскости, а ребра – линиями, соединяющими соответствующие точки. Для изображения дуги используется линия со стрелкой, указывающей направление от начала к концу дуги.
На рисунке 12 изображен смешанный граф с вершинами v1, v2,¼, v6, ребрами e1, e2, e3, e5 и дугой e4. Смежные вершины v1, v2, инциденты ребру e1. Вершины v1, v3, инциденты параллельным ребрам e2 и e3. Вершине v4 инциденты петля e5 и дуга e4, причем v4 является началом дуги e4, а v5 – концом этой дуги. Степень вершины v1 равна 3, вершины v2 – 1, вершины v3 – 2, вершины v4 – 3, вершины v5 – 1, вершины v6 – 0. Таким образом, вершины v2 и v5 – висячие, а вершина v6 – изолированная. В случае дуги e4 точнее было бы говорить о полустепенях исхода и захода вершин v4 и v5, а именно: полустепень исхода вершины v4 равна 3, вершины v5 – 0, полустепень захода вершины v4 равна 2, вершины v5 – 1.
2) Аналитический способ.
3) Матричный способ.
Имеется несколько вариантов задать граф матрицей. Наиболее употребимыми являются матрица инциденций и матрица смежности.
а) Матрица инциденций – это прямоугольная матрица, число строк которой равно числу вершин, а число столбцов – числу дуг (ребер) графа. Элементы этой матрицы определяются следующим образом:
Таким образом, для графа на рисунке 12 матрица инциденций такова:
| e1 | e2 | e3 | e4 | e5 |
| v1 | ||||
| v2 | ||||
| I= | v3 | |||
| v4 | ||||
| v5 | -1 | |||
| v6 |
По этой матрице легко судить о наличии в графе параллельных ребер (два одинаковых столбца), петли (одна единица в столбце), дуги (значения разных знаков в столбце), изолированной вершины (нулевая строка), висячих вершин (одно ненулевое значение в строке).
б) Матрица смежности вершин – это квадратная матрица, размер которой определяется числом вершин в графе. Элементы этой матрицы определяются так: 
. Если в графе имеются параллельные ребра, то соответствующий элемент матрицы смежности полагают равным числу этих ребер. Так матрица смежности для графа на рисунке 12 такова:
| v1 | v2 | v3 | v4 | v5 | v6 |
| v1 | |||||
| v2 | |||||
| S= | v3 | ||||
| v4 | |||||
| v5 | |||||
| v6 |
По виду этой матрицы также несложно судить о наличии в графе кратных ребер, дуг, петель, висячих и изолированных вершин.
Дата добавления: 2015-10-19 ; просмотров: 17498 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ
Источник
