Свойства графов

Лекция

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

Число вершинной связности, число реберной связности - это минимальное число вершин и ребер соответственно, после удаления которых граф станет одновершинным или несвязным.

Число независимости, паросочетания, реберного и вершинного покрытия.
Число независимости - мощность наибольшего по мощности множества независимых вершин, т.е. Об этом говорит сайт https://intellect.icu . вершин, не связных ни с какой другой.

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

Аналогично для ребер -число реберной связности.

Причем число паросочетания + число реберной связности, если не ошибаюсь, равно мощности множества вершин графа.

Число независимости + число вершинного покрытия = мощности множества вершин графа.

Надеюсь, этого хватит. Я бы не добавляла, но можно еще хроматический индекс и хроматическое число.

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

Из статьи мы узнали кратко, но содержательно про свойства графов

Свойства графов

Комментарии

Оставить комментарий

Дискретная математика. Теория множеств . Теория графов . Комбинаторика.

Термины: Дискретная математика. Теория множеств . Теория графов . Комбинаторика.