tgoop.com/ds_interview_lib/729
Last Update:
Какие типы графов как структур данных существуют?
Рассмотрим разные способы классифицировать графы.
▪️По кратным рёбрам и петлям
• Обыкновенные графы: рёбра между двумя вершинами уникальны, петли отсутствуют. Например, транспортная сеть с единственным маршрутом между точками.
• Мультиграфы: допускают кратные рёбра, но без петель. Пример: транспортные сети с несколькими маршрутами между городами.
• Графы с петлями: рёбра могут соединять вершину саму с собой. Подходят для моделирования самоотношений, например, повторного взаимодействия пользователя с объектом.
• Пустые графы: графы без рёбер, только изолированные вершины. Встречаются в теории графов для анализа крайних случаев.
▪️По направленности рёбер
• Неориентированные графы: рёбра двусторонние. Например, социальные связи, где дружба взаимна.
• Ориентированные графы: рёбра имеют направление. Пример: денежные переводы между людьми, где важно указать отправителя и получателя.
▪️По связности
• Связные графы: от любой вершины можно добраться до любой другой. Пример: транспортная сеть, обеспечивающая доступ между всеми городами.
• Сильно связные графы: каждая вершина достижима из любой другой с учётом направлений рёбер. Пример: система внутренних сообщений в компании.
• Слабо связные графы: связность достигается при игнорировании направлений рёбер. Пример: подписки в социальных сетях.
▪️По полноте
• Полные графы: каждая пара вершин соединена рёбрами. Используются для анализа всех возможных связей, например, в задачах кластеризации данных.
#математика
BY Библиотека собеса по Data Science | вопросы с собеседований
Share with your friend now:
tgoop.com/ds_interview_lib/729