На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> k-дольные графы (к = 3)
    Всем хай! Сходу к делу!

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

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

        еще доп.вопрос про четность циклов.
        2 определения видел про четность циклов:
        1) цикл с четным числом вершин называют четным циклом
        2) Длиной цикла называется число ребер в этом цикле. Т е, если кол-во ребер четно, то и цикл четной длины.

        Цикл включает в себя дважды стартовую вершину, например: x1 - x2 - x3 - x11 - x7 - x1 (6 вершин) или х1 надо считать один раз?
        Кол-во ребер в этом цикле = 5, т е это цикл нечетной длины

        какое определение более точное или они на 100% синонимичны???
        Прикреплённая картинка
        Прикреплённая картинка


        Добавлено
        -------------------
        еще вопрос: что такое висячее ребро? (чет не гуглится)
        висячая вершина понятно - вершина, имеющая степень = 1
          Цитата FasterHarder @
          когда читал теорию про к-дольные графы, там все свелось к раскраске и пр.

          Это то же самое. Считай, что вершины одного цвета принадлежат одной группе.

          Цитата FasterHarder @
          Цикл включает в себя дважды стартовую вершину, например: x1 - x2 - x3 - x11 - x7 - x1 (6 вершин) или х1 надо считать один раз?

          Странный вопрос. Если считаешь дважды, то тогда чётный цикл по одной версии определения будет нечётным по другой, и наоборот. А если один, то они эквивалентны. Никто в здравом уме не будет вводить две версии одного определения, которые бы означали строго противоположное, так что, разумеется, один раз надо считать.

          Цитата FasterHarder @
          еще вопрос: что такое висячее ребро? (чет не гуглится)

          В каком контексте ты это определение видел?
          На картинке у тебя трёхдольный граф, всё верно
            Цитата FasterHarder @
            еще вопрос: что такое висячее ребро? (чет не гуглится)
            висячая вершина понятно - вершина, имеющая степень = 1

            ЕМНИП висячее ребро - это ребро, хотя бы одна из вершин которого - висячая.
              Цитата Akina @
              ЕМНИП висячее ребро - это ребро, хотя бы одна из вершин которого - висячая.

              Кстати, я абсолютно согласен с этим определением, т к оно предельно логичное :yes:

              зы: а почему я сам не додумался до этого)
              Скрытый текст

              Akina, вопрос к тебе, как к модератору раздела: у меня по графам может быть сотни вопросов "мелких" и не очень, может в одной теме я буду их создавать, чтобы не плодить новые темы в "Алгоритмах", а то скоро все страницы будут только от меня в этом разделе - как мне кажется, например, для вопроса типа "Четность циклов" не стоит посвящать отдельную тему. А подобных вопросов по графам может быть оч.много...
              0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
              0 пользователей:


              Рейтинг@Mail.ru
              [ Script execution time: 0,0502 ]   [ 19 queries used ]   [ Generated: 28.03.24, 17:43 GMT ]