Господа, если не сложно, подскажите пожалуйста, а то голова разрывается не могу сообразить, а гугл что–то не помогает.

Вот смотрите, у нас есть граф G:N,E), в котором N={a,b,c,d,e}; E={(a,b),(d,e),(c,e),(d,d),(a,c),(b,d),( e,a)}

Выглядит он как–то так:

И есть вот такой подграф.

И я вот никак не могу понять, с учетом того, что в этом подграфе нет цикла у вершины «d», он будет все равно считаться подграфом G или нет?

Ну, или ссылку какую–нибудь дайте, по которой будет ясно, и, желательно, по–русски об этом написано.
пардон за корявые рисунки

GD Star Rating
loading...
Tagged with →  

24 Responses to Граф и подграф

  1. Taova:

    Подграф исходного графа — граф, содержащий некое подмножество вершин данного графа и некое подмножество инцидентных им рёбер.

    Т.е. ребер может быть вообще не быть. V = {C, E}, E = {} — подграф синей фигни.
    Т.е. вершин тоже может не быть. V = {}, E = {} — подграф синей фигни.

    Но в подграфе не может ребер, которых нет и в исходном графе.
    Но в подграфе не может вершин, которых нет и в исходном графе.

    Это все очень просто, выходит из определения графа. Всё это же множества…

  2. GoBam:

    ах вот оно что, то есть подграф это любые вершины с любым количеством ребер, главное, чтобы эти вершины и ребра были частью исходного графа. то есть, если будет, например, только вершина d с петлей, это тоже будет подграф, так?

  3. SpMonkey:

    да, так…, но стоит учесть:
    1. Подграф — это минимум одна вершина исходного графа, несмотря на то что сказал Акробат. Ибо подграф — это граф. Граф по определению это совокупность вершин, множество вершин не должно быть пустым. Иначе это уже не граф. Множество ребер может быть пустым, но не вершин.

    2. Вершина А и ребро–петля от вершины D — не будут являться подграфом исходного графа, т.к. опять же они не будут являться графом по определению.

  4. Taova:

    1. Да, я ошибся, конечно же. Всё же графы это не просто множества, иначе о них как о отдельном объекте и не говорили бы. Спасибо что заметили и поправили.

    2. Да, ребра должны быть инцидентны вершинам.

  5. GoBam:

    спасибо, вы клевые.

  6. Rafol:

    Это как определять. Некоторые авторы допускают графы с пустым множеством вершин.

  7. SpMonkey:

    Граф не может иметь пустое множество вершин, только ребер.

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

    Есть такая вещь как пустой граф или нуль–граф — это вполне несвязный граф, т.е. регулярный граф степени 0, т.е. без ребер.

    Я ни разу не встречал определения графа в котором допускалось пустое множество вершин, приведите пример пожалуйста?

  8. Peels:

    приведите пример пожалуйста

    Позвольте я приведу вам такой пример:

    Определение: Пусть V — произвольное множество, и пусть E \subset V * V. Пару G = (V, E) будем называть (направленным) графом.

  9. SpMonkey:

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

    Я встречал определения, где вопросы непустоты множества вершин как–то опускаются, но нигде не встречал чтоб как–то отдельно выделяли возможность этого.

    Давайте размышлять логически.

    1. Пустое множество — существует по крайней мере одно. По определению пустого множества из теории множеств. Теория графов оперирует теми же множествами.
    2. Через аксиому объемности — считаем что пустое множество существует, и единственно.
    3. Считаем что множество вершин — пустое множество.
    4. Тогда из определения графа — множество ребер — пустое множество.
    5. Тогда — множество ребер == множество вершин == (/). А по определению графа — они как бы не равны.
    6. Как–то не согласуется.

    Но может быть я не прав, я не настоящий математик, я дискретный 🙂

  10. Re:

    В английской википедии ничего про непустоту множества вершин нет, более того, граф без вершин и ребер они называют null–graph

  11. Peels:

    А по определению графа — они как бы не равны.
    Где вы это в приведенном определении видели?

    Нет, конечно если очень нужно, можно определить граф как структуру с обязательно непустым множеством вершин. Вот только я сейчас не припомню где бы такое ограничение было бы вообще нужно. Есть хоть какой–нибудь алгоритм или теорема, которая нуждается в этом уточнении?

  12. SpMonkey:

    нуль–граф, я уже писал выше — в российской литературе — граф без ребер. т.е. это регулярный граф степени 0.

  13. SpMonkey:

    Не смею не согласиться, я тоже не припоминаю теорем или алгоритмов на которые повлияла бы пустота множества вершин.

    Источник оригинальный 🙂 но хотелось бы ссылку на учебник, можно западный.

    В свою очередь хочу процитировать один учебник, правда щас не могу найти ссылку на оригинал, осталась только история в аське 🙁 но если очень важно, то найду.

    A nuisance in first learning graph theory is that there are so many definitions. They all
    correspond to intuitive ideas, but can take a while to absorb. Some ideas have multiple
    names. For example, graphs are sometimes called networks, vertices are sometimes
    called nodes, and edges are sometimes called arcs. Even worse, no one can agree on the
    exact meanings of terms. For example, in our definition, every graph must have at least
    one vertex. However, other authors permit graphs with no vertices. (The graph with
    no vertices is the single, stupid counterexample to many wouldbe
    theorems— so we’re
    banning it!) This is typical; everyone agrees moreorless
    what each term means, but disagrees
    about weird special cases. So do not be alarmed if definitions here differ subtly
    from definitions you see elsewhere. Usually, these differences do not matter.

    Т.е. я в целом понимаю и соглашусь пожалуй с тем, что сугубо формально, множество вершин может быть пустым. Однако тут нужно иметь немножко большую компетенцию в связанных областях (топология, гомология, абстрактная алгебра), чем я обладаю. Может быть вы более компетентны и расскажите мне что все нормально и согласуется с другими областями.

    Некоторые теоремы и алгоритмы толкаются от того, что простой граф — одномерный симплициальный комплекс. Может ли компекс состоять из пустого множества симплексов? Соответсвенно входящие симплексы должны иметь две точки — могут ли эти две точки совпасть? (хотя второй вопрос не влияет на теор. графов 🙂 )

    Некоторые теоремы и алгоритмы определяют граф — как тройку (V, E, f), где V — множество вершин, E — множество ребер, а f — функция инциндентности.
    Отсюда я бы сказал что множества V и E не равны опять же.

    Но согласно вашему определению, действительно множество вершин может быть пустым.

  14. SpMonkey:

    Ещё раз подчеркну, я ни разу не встречал определения графа с пустым множеством вершин. Но зацепившись за эту тему, увидел, что действительно некоторые авторы (я правда так и не увидел бумажной или электронной версии какого–нибудь авторитетного источника), но некоторые места в интернетах действительно определяют граф без ограничения на непустоту множества вершин.

    Однако я не согласен с такими определениями, как с не имеющими смысла в рамках теории графов.

    Я действительно ошибся, достаточно категорично ответив на фразу loraf’a.

    Я попытался найти логические нестыковки с другими дисциплинами, но к сожалению не совсем компетентен в них.
    Мне всё ещё хочется понять до конца, со всем ли стыкуется возможность пустоты множества вершин в графе.

  15. Peels:

    Вопрос сродни спору о том, нужно ли включать ноль в натуральные числа, или нет. Может быть иногда нужно, иногда — нет. В каждом конкретном случае можно отдельно уточнить.

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

    С другой стороны, если вы должны время от времени оперировать фразами в духе «пусть C — подмножество вершин, выбранное по критерию Х, расмотрим индуцированный на множестве С граф», то вам стоит разрешить пустые графы, иначе придется каждый раз объяснять что делать, если не найдется вершин, удовлетворяющих условию Х.

    В данном посте имеет смысл использовать второе определение как более простое.

  16. SpMonkey:

    Ну по поводу нуля, насколько я помню, в различных теориях есть различные определения множества натуральных чисел.
    В арифметике по аксиоматике Пеано — ноль не входит.
    В теории множеств, где натуральное число — мощность множества — ноль входит.

    Но тут всё гораздо уже. Теория графов не такая уж и большая. И я не могу вспомнить ни одну теорему или алгоритм, где граф может не иметь вершин.
    Вопрос как дальше классифицировать такой граф, какие свойства он проявляет? Тут и с классификацией сложности. По факту граф без вершин — будет простым, регулярным, нуль–графом. Какой степени? Как раскрашиваемым, сколь хроматическим? Тогда в понятие пути так же нужно включать возможность того, что путь будет содержать пустое множество элементов, и эйлеров цикл, и гамильтонов цикл, ибо у них тоже мощность множества входящих вершин снизу не ограничена.

    Я отдельно не анализировал, но думаю, что у многих алгоритмов возникнут проблемы с остановом.

  17. SpMonkey:

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

    Лучше привести чуть более конкретный пример 🙂 простите за занудство..

  18. Peels:

    Практический смысл лишь в том, что фраза
    «пусть V — множество» короче фразы «пусть V — непустое множество».

    Если нам без разницы какую выбирать, имеет смысл выбрать первую.

    И я не могу вспомнить ни одну теорему или алгоритм, где граф может не иметь вершин.

    А мне вот как раз наоборот кажется — я не могу вспомнить ни одну теорему или алгоритм, который бы требовал оговорок для пустого графа.

    Раскрашивание для пустого графа определяется так же как и любая другая функция на пустом множестве. Такая функция существует лишь одна, и она пустая.

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

  19. Rafol:

    Полностью согласен. Кстати, на пустом графе тоже понятно что такое путь. Путь — это отображение из множества {0, 1, …, n–1} в V с понятными свойствами. Значит если V = 0, то путей длины n > 0 не будет, а будет единственный путь длины 0, равный пустому множеству.

    Почему в аксиоматике Пеано нет 0? Его нет в русской Википедии, но есть в английской)? Кстати, в теории множеств, натуральные числа, это не просто мощности множеств, это, по определению, все конечные ординалы.

    Мне видится, что споры в подобных случаях не имеют смысла. Тут нельзя сказать, что правильно, а что нет. Речь может идти только об удобстве или естественности, причем может статься, что в разных случаях удобными будут противоположные подходы. Подобные предельные случаи никак не могут сказаться на теоремах и алгоритмах, они всегда тривиальны. Например, доказательство гипотезы 4–х красок для всех непустых графов не мене ценно, чем доказательства этой гипотезы для всех графов, в том числе и пустого.

  20. SpMonkey:

    Ну я как бы признал уже что был не прав, и не спорю, а скорее задаю вопросы, надеюсь Peels это понимает 🙂

    Ответы ваши мне понятны, просто не укладываются с моими знаниями, вот и все, поэтому я пытаюсь найти что–то что не приемлет пустоты множества вершин, пока не выходит 🙂 и вряд ли выйдет.

    Про путь давайте отдельно. Если мы считаем что путь нулевой длинны существует (опять же в русской педивикии считают длинной количество вершин вошедших в путь, а в онглийской написано что это кол–во ребер), то по определению пустой граф будет эйлеровым? 🙂 А гамильтоновым не будет (опять же если брать в расчет, что гамильтоновым будет путь с длинной больше 1), хотя это уже не бьется с условиями Дирака и Оре. Как быть? Мне кажется с путем не все так просто. Если брать русские материалы, то ограничение на непустоту множества вершин, решает проблему пустоты пути. В английском варианте отдельно прописано, что путь должен содержать начальную и конечную вершину.

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

    Кстати какого будет хроматическое число пустого графа?

    Простите за сумбурность 🙂 Мне приходится занудствовать 🙂

  21. Peels:

    Кстати какого будет хроматическое число пустого графа?

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

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

    Если ты определяешь раскраску как функцию, которая для каждой вершины графа задает цвет и хроматическое число как |Image(f)|, то такое определение сработает и для пустого графа. Его хроматическое число будет 0.

    Еще раз — как удобнее, так и определяй. Вопросы «ну а какое хроматическое число на самом деле» бессмысленны.

  22. SpMonkey:

    да понимаю я о чем вы вещаете, честно… наверное я зануда тогда или тролль 🙂 простите уж.

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

    Я понимаю, что здесь беда в несогласованности определений разных авторов, один ограничил другой нет, а ограничивать начинает уже позже через другие определения и условия в теоремах и алгоритмах.

    Но видимо вы меня тоже не хотите понять. Я вам хочу объяснить, что в рамках теории графов, пустой граф никакой практической и теоретической ценности не несет. Посему, ПО МОЕМУ СУГУБО ЛИЧНОМУ МНЕНИЮ, целесообразнее изначально в определении графа задать его непустоту.

    Так уж получилось, что в моей голове фраза «захочешь так повернешь, захочешь так» никогда не является приемлемым ответом на вопрос «зачем?».

    Ну да ладно. Спасибо за ответы в любом случае 🙂

  23. Peels:

    Если в этом определении я вдруг поменяю формулировку, то необходимо для всей остальной теории в рамках которой я работаю

    Да нет, конкретно от того, разрешишь ли ты пустой граф или нет ничего нигде не разъедется.

    Я вам хочу объяснить, что в рамках теории графов, пустой граф никакой практической и теоретической ценности не несет.

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

    зачем?

    На этот вопрос тебе уже ответили — определение «граф может быть всяким» по формулировке проще, чем определение графа с ограничениями, а по свойствам ничуть не хуже. Из более хорошего и более простого определения лучше выбрать то, что получше.

  24. SpMonkey:

    Все что сказали субъективно, как и мое мнение, посему думаю спорить наверное дальше бессмысленно.

    Но по одному моменту таки возражу:
    Да нет, конкретно от того, разрешишь ли ты пустой граф или нет ничего нигде не разъедется

    Поедут определения связанные, путь, цикл, хроматическое число и другие. Именно определения. Поедет классификация эйлеров, гамильтонов, ориентированный, полный и т.д. Оценочные критерии поедут и их доказательства, как я уже говорил выше, например Дирака или Оре.

    Все эти вещи увязаны в рамках одной теории (конкретного экземпляра теории графов, или курса или книги, или похер чего) но если мы будем там и сям брать определения из разных теорий у нас много чего может поехать.

    Ну да ладно. В целом я с ваше мнение понял и согласился. 🙂

Добавить комментарий