Комментарии 19
Мне кажется, одна из серьёзных проблем любой статьи про графы в том, что после "введения в графы", когда даётся 2-3 примера, дальше всё вываливается сухим потоком.
Если бы каждый случай разбирался "из практики" (ну вот где у вас плотные графы на существенные размеры бывают? Я вот с ходу и придумать не могу), да ещё и с описанием "плохих" попыток, то наглядность была бы значительно выше.
Согласен. Сожалею, что не могу голосовать.
Думаю, что да. Люди бы более яснее понимали, почему лучше использовать именно этот метод и тд. Возможно в последующих статьях я попытаюсь сделать, что-то подобное. Наверное это будет очень не скоро, но пока все что есть. Здесь я попытался в максимально доступной форме объяснить, как же это делать. И в первую очередь я делаю это для студентов, которые изучают данную тему и могут не понимать, зачем вообще графы нужны. Учась, я лично убедился, что для многих эта тема была "проходной" и они не извлекли из нее никакой ценной информации, а также так и не поняли, как работать с матрицами.
И в первую очередь я делаю это для студентов, которые изучают данную тему и могут не понимать, зачем вообще графы нужны.
ИМХО для IT-студентов нужно сразу сказать, что списки (стеки, очереди) и бинарные деревья это графы. И всякие схемы, типа схемы метро, автодорог, принципиальные в электронике можно рассматривать как графы. Приложения теории графов — это фундаментальные свойства всяких подобных схем.
Для студентов историков м.б. будет полезно узнать, что фамильные деревья — это графы. И проч. др. специальности. Где только нет графов, пусть на уровне тривиального списка. Возвращаясь к IT: строка символов — граф. и число — последовательность байт — граф, и файл — граф, не говоря о БД.
Вы знаете, не все учителя преподающие в учебных заведениях, могут обладать столь широкими познаниями в графах, также теория графов, к сожалению только одна из тем в большом предмете под названием дискретная математика и не многие учителя могут раскрыть эту тему полностью, из-за нехватки времени.
Также хочу отметить, что наша беседа описанная чуть ниже не приведет к конкретным выводам так как сама теория графов очень неоднородна и у каждого человека свои мнения, тоже касается и авторов. Делая статьи я не придумаю каких-либо правил, а использую имеющиеся у меня ресурсы для того, чтобы создать статью удовлетворяющую все стороны (ну или постараться это сделать). Следуя этому ваше сообщения, где как кажется вы подчеркнуто выделили "Ваш подход" выглядит неуместно и честно не слишком приятно. Создавая статьи, я также использую учебник Харари. То о чем вы говорите находится у него отдельной темой "Орграфы" и подзаголовок обозначен там, как "Орграфы и матрицы" я читал этот раздел и отдельно главу про матрицы, но для статьи решил ничего оттуда не брать и обратится к другим источникам, где нашел описанную мною информацию. Это не значит, что мне нравится его формулировка, это значит, что я выбрал в качестве описание, отличное от него в некоторых аспектах описание. И думаю, что на этом наше противоречие стоит остановить, ибо мы уже итак нарушили закон логики, но также не сможем выявить чье мнение истинно, так как оба заслуживают жизнь. Спасибо за замечания и высказанную точку зрения!)
не все учителя преподающие в учебных заведениях, могут обладать столь широкими познаниями в графах, также теория графов, к сожалению только одна из тем в большом предмете под названием дискретная математика и не многие учителя могут раскрыть эту тему полностью, из-за нехватки времени.
Совершенно с Вами согласен. Преподаватели непрофильных для вуза предметов часто не имеют представления об интересах студентов, которых учат. Вспоминаю, что на 5 курсе ХФ МГУ к нам пришла молодая девушка, почти нашего возраста, учить нас английскому. Она рассказала нам, что только что закончила иняз, и диплом у нее был по Шекспиру. Язык она знала очень хорошо, но не химический. А химию она не знала — со школы успела забыть, что знала. А у нас были методички с текстами из научных хим. журналов. Думаю, что это было большое упущение нашего деканата: на факультете было много химиков, которые хорошо владели английским. Нужно было к таким учителям английского, как наша девушка, приставить консультантов, которые бы помогали в переводе хим.текстов и, что самое важное, объясняли на русском хим. смысл. Аналогично с учителями дискретной математики. Каждый человек приходя на новую работу должен изучить специфику. Лектор, который чисто формально читает студентам теорию графов и не думает об адресации, поступает плохо. Мог бы сам в деканат обратиться с просьбой дать консультанта.
не многие учителя могут раскрыть эту тему полностью, из-за нехватки времени.
У лектора должно быть время на подготовку, которое ему оплачивают, как и лекцию. Если лектор еще где-то работает по совместительству, то это его выбор — придеться перерабатывать.
Следуя этому ваше сообщения, где как кажется вы подчеркнуто выделили "Ваш подход" выглядит неуместно и честно не слишком приятно.
Честно: очень сожалею, о том, что показалось Вам не приятным. Правда, я не понял, какие именно слова Вам не приятны. Если про методологию, то с моей стороны это был скорее вопрос, а не утверждение. Я привел пример иных методологических подходов и ожидал от Вас услышать обоснование Вашего. Это наука, и ничего личного. Если кто-то напишет, что дважды два пять, и я спрошу: нет ли у Вас здесь ошибки? А он ответит, что я задал не приятный вопрос. Думаю, что всем участникам обсуждения станет не очень приятно.
вы подчеркнуто выделили "Ваш подход"
Я не могу назвать его своим подходом, т.к. его придумали до меня, и я указал на авторов. Но принимаю Ваш вывод:
оба заслуживают жизнь
Спасибо!
Не понял:
в неориентированном графе петля учитывается дважды
Пусть в графе 4 вершины и только одна петля у вершины 1, других ребер нет, тогда м-ца смежности будет иметь 1 в первом элементе (1,1), все остальные будут нули.
Не понял список смежности для первого графа в секции. На рисунке ребро 1-4 кратное, и нет ребра 2-3. Если сделать ребро 1-4 не кратным, то список можно записать проще и экономнее: 1-2, 1-3, 1-4, 2-4, 3-4, всего 5 ребер. А по Вашему списку их больше. Список смежности часто употребляют для ручного ввода, это бывает быстрее, чем матрицу набивать.
Касательно, списка смежности. Спасибо за найденный недочет вставил не ту картинку, уже все поменял. Касательно первого вопроса. У нас же неориентированный граф, и получается, что в вершине 1, ребро как выходит, но также и входит в него. И мы должны будем поставить 2, так как если мы захотим узнать степень вершины и как вы говорите поставим 1, то мы учтем только тот случай когда в нее входит ребро, но оно же из него и выходит, а это уже не будет учтено, что будет являться ошибкой.
В Вашем подходе неориентированный граф — частный случай орграфа: ребро выходит из в-ны 1 и заходит в 2, и другое ребро из 2 заходит в 1. На рисунке это будет со стрелочками: 1 ->2, 2 -> 1 или 1 <->2. Но это избыточно. Во многих признанных учебниках орграфы идут отдельной главой — студенту бы просто графы понять, ему не до петель! Видимо, многие авторы таких учебников (Харари, Зыков и др.) сочли бы Ваш подход методологически ошибочным.
А где вторую часть найти?
Перевернутое А зарезервировано для квантора всеобщности и при использовании в качестве имен объектов может создать существенную путаницу.
1. По поводу чисел в графах — они маленькие, а расстояния между вершинами большие. Возможно, у вас какая-то программа генерирует эти изображения. Рекомендую для статей использовать draw.io (там можно и перемещать объекты, и менять размер шрифта и др.).
2. «Но есть еще два способа как можно задавать граф, а точнее представлять его». Если можно написать точнее, то пишите без лишних слов.
3. Неправильные определения плотного и разреженного графов: «... плотных графов в которых количество ребер (E) примерно равно количеству вершин (V)» и «... разреженных графов, то есть графов где количество ребер меньше количества вершин». Откуда прямая связь с числом вершин? Плотный граф — граф, в котором число ребер близко к максимально возможному числу ребер (у полного графа) (см. определение из NIST). Разреженный граф — граф, в котором число ребер намного меньше максимально возможного числа ребер (у полного графа) (см. определение из NIST).
4. Множество орфографических, грамматических и логических ошибок.
Наиболее выделяющиеся ошибки
«Здесь отсутствует дублирование между вершинами, так как если вершина 1 соединена с вершиной 2, наоборот соединена она не может быть, так у нас есть направление у ребра». Конструкция «если ..., то» частично отсутствует.
«В вершину 1 ничего не входит, значит матрица верна». Это не вывод, вы же заранее составляете матрицу, а не доказываете её правильность.
«в нашем случаи». Должно быть «в <?> случае».
5. Перевёрнутую А не используют для обозначения матрицы. Матрицу обозначают буквой M (английской; от слова Matrix), иначе грош цена вашим обозначениям, когда они ни одному учебнику и ни одному стандарту не соответствуют.
Остальное не проверял — потерял интерес.
Теория графов хорошо проработана во многих учебниках. Не совсем понимаю, в чем смысл таких чисто теоретических статей, причем с ошибками. Желательно делать одну статью с краткой теорией и большей по объему практикой.
Upd. Также непонятно, что делает эта статья в хабах «Сетевые технологии», «Машинное обучение» и «Искусственный интеллект».
Благодарю, поменял в тексте моменты, высказанные вами в виде замечаний.
Подскажите, пожалуйста, какие материалы лучше почитать чтобы лучше понимать тему? Не только про сами графы, но и алгоритмы поверх него интересуют (dfs, bfs, поиск кратчайшего пути и т.д.).
Из классики на русском — «Фундаментальные алгоритмы на C++. Часть 5. Алгоритмы на графах» Роберта Седжвика и «Совершенный алгоритм. Графовые алгоритмы и структуры данных» Тима Рафгардена.
На английском можно найти больше книг. Можно посмотреть в сторону Amazon (в поиске есть фильтры, в том числе фильтр по целевой аудитории + отзывы развернутые). Там нужно именно выбирать книги по отзывам, а скачивать — на Libgen или на Z-Library.
Спасибо большое!
Классическая книга это:
Кристофидес, Теория графов. Алгоритмический подход, М.: Мир, 1978 (м.б. есть болеее новые переиздания).
Еще:
В.Липский, Комбинаторика для программистов, М.: Мир, 1988.
И объемный том:
В.Н.Касьянов, В.А.Евстигнеев, Графы в программировании: обработка, визуализация и применение, Спб: БХВ-Петербург, 2003.
Теория графов. Часть третья (Представление графа с помощью матриц смежности, инцидентности и списков смежности)