Введение.

ГРАФЫ

V={1,2,3,4}, E={(1, 2), (4, 3), (3, 4), (3, 1), (4, 1)}.

G(V, E), V = {a, b, c, d}, E = {(a, b), (a, c),(a, d), (d, c)}.

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

В 1999 году ICRSR были разработаны «Основные принципы подготовки социологических данных к архивированию». В них четко описаны требования по формату представления данных, перечню всех сопроводительных документов, а также информация о депозиторе этих данных. Что касается формата, то данные должны быть представлены в электронном варианте в формате SPSS или SAS, они должны сохранять конфиденциальность, если данные представлены разными файлами, то все переменные, даже общие, должны быть объяснены для каждого файла отдельно. Также должны быть указаны коды всех переменных, все производные переменные должны сопровождаться инструкцией их построения, использованные весовые коэффициенты также должны сопровождаться пояснениями. Должны быть подробно описаны способ построения выборки, методология исследования и его гипотеза. В перечень необходимой документации входят помимо самих файлов с данными схема кодировки (все коды с расшифровками), итоговый отчет, библиография публикаций, имеющих отношение к данным, итоговая расчетная статистика (таблицы, посчитанные корреляции, данные регрессионного, факторного анализа, рассчитанные индексы и коэффициенты). Обязательно представление инструментария исследования (образцы анкет, гайдов интервью, планов наблюдений, в зависимости от типа исследования). Форма депозитора должна включать в себя описание ключевых терминов, использованных в ходе исследования, впоследствии это будет использовано для классификации разных исследований по темам и построению поисковой системы по терминам, описание места и времени исследования, описание авторов исследования, его заказчиков и спонсоров, а также контакты с авторами и ссылки на их другие работы и данные.

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

Функции архивов:

1. архивная (накопление данных, их хранение, систематизация, создание поисковой системы)

2. распространение данных (доступность архивов, открытость, удобство пользования)

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

В заключение лекции обратим внимание на основные идеи и ключевые моменты. Итак, вторичный анализ – это социологический метод, с помощью которого можно решать новые исследовательские задачи на основе старых, вторичных данных. Он был разработан в США, где и достиг максимально развития, в России этот метод пока переживает период своего становления и институциализации. Основными преимуществами применения вторичного анализа являются экономия средств, высокая достоверность данных, возможность описывать сложные и масштабные проблемы, обеспечивать многостороннее описание предмета исследования и воспитание культуры обращения с социологической информацией.

Литература

1. Добреньков В.И.,Кравченко А.И. Методы социологического исследования. Учебник - М.: Инфра-М, 2004,786 с.

2. Ростегаева Н.И. Банк социологических данных: проблемы функционирования и тенденции развития. Социология 4М: методология, методы, математические модели. №10. 1998

3. Сазонов Б.В. Вторичный анализ данных - новый подход к организации социальных исследований. М., УРСС, 1997.

4. Социальная информатика. Основания, методы, перспективы. Отв. ред. Лапин Н.И. - М., 2003.

5. Сычева В.С. Вторичный анализ как метод. СОЦИС, 1995, N 11, с. 128-131.

6. Татарова Г.Г. От постулатов эмпирической социологии к методологии анализа данных. Социология. 4, М.: 1999. №11. С. 51-71.

7. Хахулина Л.А. Создание общедоступного социологического архива в России. Экономические и социальные перемены: Мониторинг общественного мнения.- 2002.- 2. - С. 54-57.

8. Шляпентох В.Э. Маслова О.М.. К вопросу о сопоставимости результатов социологических исследований. СОЦИС, 1975, N3, с 20-34.

Граф можно изобразить диаграммой следующим образом:

Вершины изобразить точками и кружками; ребра изобразить линиями.

Число вершин обозначается p(G) = |V|.

Число ребер графа q(G) = |E|.

Пусть vи uвершины графа, e = (v, u) это ребро графа, тогда вершина vи ребро eназываются инцидентными, вершина u и ребро eтак же инцидентные.

Два ребра инцидентные одной вершине называются смежными.

Две вершины инциденты одному ребру называются смежными.

Степенью или валентностью вершины называется количество ребер инцидентности этой вершины d(V).

Регулярным графом степени k называется граф, степени всех вершин которого равны k .

Вершина называется изолированной, если ее степень равна 0.

Вершина называется висячей, если ее степень равна 1.

Петлей называется ребро, начинающееся и заканчивающееся в одной вершине.

Кратными ребрами называется ребра инцидентные одной и той же паре вершин.

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

Граф называется полным, если любая пара вершин соединена одним ребром.

Тема. Маршруты, цепи, циклы

Маршрутом в графе называется последовательность вершин и ребер v₀ v₁ v₂ v₃ …v_n.

Длиноймаршрута называется количества ребер в нем.

Маршрут, в котором все вершины различны, называется простой цепью.

Замкнутая простая цепь называется простым циклом.

Замкнутая цепь называется циклом.

Расстоянием между вершинами u и v называется длина кратчайшей цепи d(u, v).

Кратчайшая цепь, соединяющая вершины называется геодезическая.

Диаметром графа G называется длина длиннейшей геодезической цепи.

. Орграф

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

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

Началом ребра называется вершина, указанная в паре первой, концом – вторая вершина этой пары (графически она указана стрелкой).

Ребра при изображении ориентированных графов представляют стрелками.

ПРИМЕР

G(V,E) - орграф.

Ребро ориентированного графа называетсядугой.

Если вершины u и v определяют дугу, то вершина u называется антицидентом вершины v.

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

Дуги орграфа называются кратными, если они имеют одинаковые начальные и конечные вершины, то есть одинаковые направления

Контуром в ориентированном графе называют путь начинающейся и заканчивающейся в одной вершине.

Граф, в котором нет контура, называется безконтурным.

Способы задания графов

Во многих задачах, особенно, решаемых на ЭВМ, графы удобно описывать матрицами.

1.Задание графов матрицей смежности:

Матрица смежности– это квадратная матрица порядка p(количество вершин), элемент которой, стоящий в i строке и j столбце определяется по правилу:

ПРИМЕР

2. Задание графов матрицей инциденций.

Матрицей инцидентции называется прямоугольная матрица размерности (p – количество вершин, q – количество ребер), элемент которой стоящий в i строке и j столбце определяется по правилу:

- для неориентированного графа.

- для ориентированного графа.

ПРИМЕР

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

Важным при рассмотрении графов является вопрос о том, какие графы можно и нужно считать различными, а какие – одинаковыми.

Определение. Графы G’ и G’’ называютсяизоморфными, если существует взаимно-однозначное соответствие (биекция) между их ребрами и вершинами, причем ребра соединяют соответствующие вершины.

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

ПРИМЕР

Графы приведенные на рисунке изоморфны:

Связные графы

Еще один из выделяемых видов графов связан с возможностью попадания из одной его вершины в другую.

Две вершины называются связными, если существует маршрут между ними. Связность для вершин является бинарным отношением.

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

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

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

Ребро (v, u) связного графа G называется мостом, если после его удаления G станет несвязным и распадется на два связных графа G’ и G’’.

ПРИМЕР

Ребро (v₃, v₄) связного графа является мостом, т. к. после его удаления G станет несвязным и распадется на два связных графа

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

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

Любой из нас, конечно, прав,

Найдя без проволочек,

Что он … обыкновенный граф

Из палочек и точек.

Понятие «граф» – одно из самых простых и самых употребительных понятий в математике и других науках, хотя теория графов зародилась чуть ли не 250 лет тому назад в ходе решения головоломки, и тогда же появились первые теоремы о графах, доказанные самим Леонардом Эйлером.

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

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

Итак, как отдельная математическая дисциплина теория графов была представлена лишь в 30 – е годы ХХ столетия в связи с тем, что в обиход вошли так называемые «большие системы», т.е. системы с большим числом объектов, связанных между собой разнообразными соотношениями: сети железных дорог и авиалиний, телефонные узлы на много тысяч абонентов, системы заводов – потребителей и предприятий – поставщиков, радиосхемы, большие молекулы и т.д. и т. п. Стало ясно, что разобраться в функционировании таких систем невозможно без изучения их конструкции, их структуры. Здесь и пригодилась теория графов. В середине XX века задачи теории графов стали возникать также и в чистой математике (в алгебре, топологии, теории множеств). Чтобы можно было применять теорию графов в столь разнообразных областях, она должна быть в высшей степени абстрактной и формализованной. Ныне она переживает эпоху бурного возрождения.

Графы используются: 1) в теории планирования и управления, 2) в теории расписаний, 3) в социологии, 4) в математической лингвистике, 5) экономике, 6) биологии, 7) химии, 8) медицине, 9) в областях прикладной математики таких, как теория автоматов, электроника, 10) в решении вероятностных и комбинаторных задач и т.д.

Наиболее близки к графам – топология и комбинаторика.

Хронологически первой в теории графов считается задача о семи кенигсбергских мостах, которую решил Эйлер. Она состоит в следующем. Парк города Кенигсберга был расположен на обоих берегах реки Прегель и на двух островах. Острова с берегами и друг с другом были соединены семью мостами так, как на рис. 1. Любимой забавой горожан были поиски такого маршрута, который кончался бы на том же берегу, где и начинался, проходил бы по всем мостам, но по каждому мосту – только один раз. Возможен ли вообще такой маршрут?

Для удобства решения составили схему или диаграмму. Части суши (оба берега и острова) обозначили точками А, В, С, D, а пути их соединяющие и проходящие по мостам, изобразим линиями, соединяющими эти точки. (Рис. 2) Такая схема содержит всю необходимую информацию о рассматриваемой ситуации и не содержит ничего лишнего. Глядя на нее, можем заключить только, что четыре объекта – А, В, С, D – попарно как-то связаны между собой ( в данном случае мостами), причем А с В и В с С соединены двойной связью, а D с каждым из объектов А, В и С – одинарной. Точки А, В, С, D – вершины, соединяющие их линии – ребра диаграммы.

Задача будет решена в ходе работы над схемой рисунка 2. (показано позднее)

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

П. 1. Основные понятия.

Определение 1. Будем говорить, что задан граф G, если задано конечное множество и некоторое множество W неупорядоченных пар различных элементов из V: . Таким образом, граф – это упорядоченная пара . Элементы множества V называют вершинами графа, а заданные пары этих элементов – ребрами. Множество ребер W, соединяющих элементы множества V, отображают это множество само в себя.

Замечание. Определение графа совпадает с определением отношения на множестве. Граф – бинарное отношение на множестве V , т.е. подмножество R множества (множество всех упорядоченных пар вида , где ).

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

Определение 1^’. Граф представляет собой непустое множество точек и множество отрезков прямых или кривых линий, оба конца которых принадлежат заданному множеству.

Определение 2. Граф с p вершинами и q ребрами называется (p, q) – графом.

Обозначения: граф – G или Г;

вершины – заглавными различными буквами А, В, С …, или маленькими различными буквами, или одинаковыми буквами с индексами х₁, х₂,... или числами 1, 2, 3…;

ребра – (А,В) или , или , или (х₁, х₂), или (1,2) (отрезки или дуги , соединяющие вершины) или просто u₁, u₂…(первое ребро, второе и т.д.)

Изображение. Точки – вершины – выделяют кружочками или квадратиками. Ребра, соединяющие некоторые вершины, изображают отрезками прямой или дугами. Существуют вершины, которые не соединены ребрами. Они называются изолированными.

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

Пример. Построить графы: а) Г = , b) .