Граф отношений между людьми

Граф как модель отношений

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

Если граф описывает знакомства людей, то вершины — это люди, а ребро между двумя вершинами означает, что эти люди знакомы друг с другом.

Пример графа знакомств

Пусть в классе четверо: Аня, Боря, Вера и Гена. Известно, кто с кем знаком. Это можно записать таблицей, где «да» означает знакомство.

По таблице легко построить граф: проводим ребро там, где в клетке стоит «да».

Виды отношений

Отношение «знаком» взаимное: если Аня знакома с Борей, то и Боря знаком с Аней. Такие связи рисуют простой линией без стрелки. А отношение «старше» направленное: оно идёт от одного объекта к другому. Направленные связи изображают стрелками.

• взаимное отношение — линия без стрелки;
• направленное отношение — стрелка от одного объекта к другому;
• граф со стрелками называют направленным.

Что можно узнать по графу

Граф помогает быстро отвечать на вопросы о связях. Чтобы узнать, сколько у человека знакомых, считают рёбра, выходящие из его вершины. Чтобы понять, можно ли передать сообщение от одного к другому, ищут путь по рёбрам. Например, Аня не знакома с Геной напрямую, но может передать письмо через Борю или через Веру.

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

Другие отношения через граф

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

• родственники — вершины люди, рёбра связи «родитель» или «брат»;
• города — вершины города, рёбра дороги между ними;
• команды — вершины игроки, рёбра «сыграли матч».

Правило: по графу удобно отвечать на вопросы вида «через сколько знакомых Аня может передать письмо Гене». Для этого ищут путь по рёбрам от одной вершины к другой и считают число рёбер в пути.

Кратко о главном

• Граф — это вершины (объекты) и рёбра (связи между ними).
• Отношения между людьми удобно описывать графом или таблицей.
• Взаимные связи рисуют линией, направленные — стрелкой.
• По графу можно искать пути и отвечать на вопросы о связях.