На четырёх рисунках ниже предоставлены следующие схемы:
Семья Бернулли дала миру девять известных физиков и математиков. Якоб Бернулли по праву считается одним из основателей современной теории вероятностей.
У всех этих схем есть общее — они показывают связи между отдельными элементами.
•в родословном дереве линия идёт от отца к сыну
•схема молекулы показывает, в каком порядке связаны между собой атомы углерода, водорода и кислорода.
•на схеме метро связи — переходы и перегоны между соседними станциями,
•радиосхема показывает, как соединить между собой радиодетали, чтобы получился работающий прибор.
Для изображения и изучения связей между различными объектами — предметами или понятиями — в математике применяется граф.
Граф — это изображение объектов и связей между ними с помощью точек и линий.
Слово «граф» происходит от латинского слова graphica — «рисование», «черчение».
Точки в графе называются вершинами графа. Некоторые (не обязательно все) вершины соединены линиями.
Эти линии называются рёбрами графа.
Если вершина является концом ребра, говорят, что ребро исходит из этой вершины, или что оно входит в неё.
Вершина не обязательно должна быть соединена рёбрами с другими вершинами.
Вершину, из которой не выходит ни одно ребро, называют изолированной.
Каждая вершина в графе должна быть явно отмечена. На рисунке рёбра могут пересекаться, но точка пересечения не является вершиной графа.
Это как две нитки: одна пересекает другую, но узелка в точке пересечения нет.
В графе важны только сами вершины и связи между ними;
взаимное расположение вершин не важно.
Можно представлять себе граф как пуговицы, соединённые длинными нитками. Пуговицы можно двигать как угодно, лишь бы нитки не рвались.
В графе важны не только сами вершины, но и связи между ними.
На рисунках ниже показаны два графа, полученные друг из друга «движением вершин».
Если в двух графах вершины связаны рёбрами в одном и том же порядке, то один граф можно получить из другого, передвигая вершины. Такие графы мы считаем одинаковыми.
Ниже одинаковые графы или различные?
Нужно стараться изображать графы как можно проще и яснее. Если с первого раза не получилось, лучше перерисовать граф в более удобном виде.
ПРИМЕР: В архипелаге шесть островов и шесть мостов: мост между островами Адуаки Бани, мост между островами Адуак и Видо, между островами Бани и Видо, между островами Екитии Гауту, между Бани и Джемии между Видои Джеми. Можно ли по мостам перейти с острова Адуакана остров Гауту?
Ответ и решение здесь.
Пример: Два чёрных и два белых коня стоят в углах шахматной доски 3x3, чёрные вверху, а белые внизу. Можно ли, передвигая их по шахматным правилам, поставить белых коней в два противоположных угла, а чёрных — в два других противоположных угла?
Ответ и решение здесь.
А продолжение статьи про графы тут.
Ну и ДЗ там.