Является ли ободом последовательность вершин

@extrimally · Регистрация: 22.09.2012

Author24 — интернет-сервис помощи студентам

Является ли ободом последовательность вершин 3-7-6-10-14-13-3 в данном графе? ОЧЕНЬ НАДО!
Обод – это граф, вершины которого V0,V1,…,Vn (n>=2) можно занумеровать так, что для всех i (1 <= i <= n-1) вершина Vi соединена с Vi-1 и Vi+1, вершина V0 с вершиной Vn и других ребер нет(т.е. цикл без лишних ребер между собой, как я понимаю)

@Igor3D · 10.06.2013, 12:20

Проблема с определением

Прочитав (неск раз) я тоже не понимаю что значит "других ребер нет"? Если "вообще никаких нет", то ободом может являться только замкнутый контур, где каждая вершина имеет строго 2 ребра. Это явно глупо, напр задача "найти все ободы в графе" тогда не имела бы смысла - "граф или обод или нет".

Поэтому остается предположить что в ободе нет никаких других ребер связывающих любые 2 вершины V0..VN, и значит последовательность вершин 3-7-6-10-14-13-3 является ободом в данном графе

@Mysterious Light · 10.06.2013, 14:52

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

Задача на нахождение всех ободов мне кажется очень интересной. Понятно, что любая точка — обод размера 1. Любое ребра — обод размера 2. Любой треугольник — обод размера 3. А дальше сложнее, потому что любой связной совокупности вершин можно сопоставить больше 1 обода, их всех обходящего, если ребер достаточно (см. Гамильтонов цикл в полном подграфе). Как решить такую задачу, кроме как полным переборам, я не знаю.

@extrimally · 10.06.2013, 15:35 **[ТС]**

Вчера начал писать код на C# для этой задачи - нахождение всех ободов. Я так и подумал про ободы. Но все-же у вас уточнил. Сейчас я почти закончил писать код

Сообщение от Mysterious Light

Понятно, что любая точка — обод размера 1. Любое ребра — обод размера 2. Любой треугольник — обод размера 3.

Обод – это граф, вершины которого V0,V1,…,Vn (n>=2) Значит минимум обод - это треугольник по определению.
в основе лежит Алгоритм поиска всех маршрутов между двумя заданными вершинами графа, то есть циклов. затем я вычислял где ободы. всем спасибо! вот код, если интересно:

Кликните здесь для просмотра всего текста

C#

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.Collections;
using System.IO;
 
namespace WindowsFormsApplication1
{
    public partial class Form1 : Form
    {
        public struct uzel
        {
            public int nom;
            public int ki;
            public int kj;
        };
        public Form1()
        {
            InitializeComponent();
        }
 
        private void button1_Click(object sender, EventArgs e)
        {
            StreamReader f1 = new StreamReader("input.txt");
            Stack vstek = new Stack();
            int i, j, k, kol;
            uzel y1 = new uzel();
            uzel n = new uzel();
            int beg, en, x, i1, i2;
            
            bool[] nov = new bool[17];
            int[,] p = new int[16, 16];
            int[] m = new int[17];
            //Матрица смежности
            string ss;
            int[,] a = new int[16, 16];
            for (int t = 0; t < 16; t++)
                for (int u = 0; u < 16; u++)
                {
                    ss = f1.ReadLine();
                    a[t, u] = Convert.ToInt32(ss);
                }
            f1.Close();
 
            for (i = 0; i < 16; i++)
            {
                p[i, 0] = i; k = 1;
                for (j = 0; j < 16; j++)
                    if ((a[i, j] != 1000) && (a[i, j] != 0))
                    {
                        p[i, k] = j;
                        k++;
                    }
                p[i, k] = 1000;
            }
 
            int[,] circles = new int[1674, 17];
            int c2 = 0;
            for (int o = 0; o < 16; o++)
            {
                beg = o;
                en = o;
                for (i = 0; i < 16; i++)
                {
                    nov[i] = true;
                    m[i] = 0;
                }
                nov[16] = false;
 
                x = 1;
                m[1] = beg; i1 = 2;
                y1.nom = beg;
                y1.ki = beg;
                y1.kj = 0;
                vstek.Push(y1);
                kol = 1;
                nov[beg] = false;
                nov[en] = false;
                i = beg; j = 0;
                while (kol != 0)
                {
                    do
                    {
                        j++;
                        if (p[i, j] == en)
                        {
                            x++;
                            for (i2 = 1; i2 < i1; i2++)
                            {
                                circles[c2, i2 - 1] = m[i2];
                            }
                            circles[c2, i2 - 1] = en;
                            circles[c2, i2] = 50;
                            c2++;
                        }
                    }
                    while ((p[i, j] != 1000) && (!nov[p[i, j]]));
 
                    if (p[i, j] != 1000)
                        if (nov[p[i, j]])
                        {
                            y1.ki = i;
                            y1.kj = j;
                            i = p[i, j];
                            y1.nom = i;
                            vstek.Push(y1);
                            j = 0;
                            kol++;
                            nov[i] = false;
                            m[i1] = i;
                            i1++;
                        };
                    if (p[i, j] == 1000)
                    {
                        kol--;
                        if (kol != 0)
                        {
                            n = (uzel)vstek.Pop();
                            i = n.ki;
                            j = n.kj;
                            i1--;
                            m[i1] = 0;
                            nov[n.nom] = true;
                        }
                    };
                }
            }
 
            int[,] obod1 = new int[254, 17];
            int fl = 0;
            for (i = 0; i < 254; i++)
                for (j = 0; j < 17; j++)
                    obod1[i, j] = -1;
            for (int d = 0; d < 1674; d++)
            {
                int s, v = 0, b, q = 0, t, nn;
                for (s = 0; s < 17; s++)
                {
                    v++;
                    if (circles[d, s] == 50)
                        break;
                }
                if (v > 4)
                {
                    if (v == 5)
                    {
                        for (s = 0; s < 4; s++)
                            obod1[fl, s] = circles[d, s];
                        fl++; continue;
                    }
 
                    for (b = 2; b < v - 3; b++)
                        if (a[circles[d, 0], circles[d, b]] == 1)
                            q = 1;
                    if (q == 1) continue;
                    for (t = 1; t < v - 4; t++)
                    {
                        for (nn = t + 2; nn < v - 2; nn++)
                            if (a[circles[d, t], circles[d, nn]] == 1)
                                q = 1;
                    }
                    if (q != 1)
                    {
                        for (s = 0; s < v - 1; s++)
                            obod1[fl, s] = circles[d, s];
                        fl++;
                    }
                }
            }
            
            int[,] obod_sort = new int[254, 17];
 
            for (i = 0; i < 254; i++)
            {
                int[] sor = new int[17];
                int s = obod1[i, 0];
                for (j = 0; j < 17; j++)
                {
                    if (s == obod1[i, j] && j > 0)
                        break;
                    sor[j] = obod1[i, j];
                }
                Array.Sort(sor);
                Array.Reverse(sor);
                for (j = 0; j < 17; j++)
                    obod_sort[i, j] = sor[j];
            }
            
            bool[] Noboda = new bool[254];
            for (i = 0; i < 254; i++)
                Noboda[i] = true;
 
            for (i = 0; i < 253; i++)
                if (Noboda[i])
                    for (j = i + 1; j < 254; j++)
                        if (Noboda[j])
                        {
                            int v = 0;
                            for (int y = 0; y < 17; y++)
                                if (obod_sort[i, y] == obod_sort[j, y])
                                    v++;
                            if (v == 17)
                                Noboda[j] = false;
                        }
            i = 1;
            for (int d = 0; d < 254; d++)
                if (Noboda[d])
                {
                    textBox1.Text = textBox1.Text + "Обод № " + i + ":   ";
                    if (i < 10)
                        textBox1.Text = textBox1.Text + "   ";
                    i++;
                    for (int r = 0; r < 17; r++)
                    {
                        if (obod1[d, r] == -1)
                            break;
                        textBox1.Text = textBox1.Text + obod1[d, r];
                        if (obod1[d, r + 1] != -1)
                            textBox1.Text = textBox1.Text + " - ";
                    }
                    textBox1.Text = textBox1.Text + "\r\n";
                }
            i--;
            textBox1.Text = textBox1.Text + "------------------------------------------------------------";
            textBox1.Text = textBox1.Text + "\r\n" + "Всего ободов в графе:  " + i;
        }
 
        private void button2_Click(object sender, EventArgs e)
        {
            Form2 f2 = new Form2();
            f2.Show();
        }
 
        private void button3_Click(object sender, EventArgs e)
        {
            Close();
        }
    }
}

Всего получилось 22 обода

@extrimally 9 / 9 / 2 Регистрация: 22.09.2012 Сообщений: 212
		1
	Является ли ободом последовательность вершин 10.06.2013, 09:56. Показов 1848. Ответов 3 Метки нет (Все метки) Является ли ободом последовательность вершин 3-7-6-10-14-13-3 в данном графе? ОЧЕНЬ НАДО! Обод – это граф, вершины которого V0,V1,…,Vn (n>=2) можно занумеровать так, что для всех i (1 <= i <= n-1) вершина Vi соединена с Vi-1 и Vi+1, вершина V0 с вершиной Vn и других ребер нет(т.е. цикл без лишних ребер между собой, как я понимаю) Миниатюры 0

@Igor3D 1823 / 731 / 99 Регистрация: 01.10.2012 Сообщений: 3,737
	10.06.2013, 12:20	2
	Проблема с определением Прочитав (неск раз) я тоже не понимаю что значит "других ребер нет"? Если "вообще никаких нет", то ободом может являться только замкнутый контур, где каждая вершина имеет строго 2 ребра. Это явно глупо, напр задача "найти все ободы в графе" тогда не имела бы смысла - "граф или обод или нет". Поэтому остается предположить что в ободе нет никаких других ребер связывающих любые 2 вершины V0..VN, и значит последовательность вершин 3-7-6-10-14-13-3 является ободом в данном графе 1

@Mysterious Light $Эксперт по математике/физике$ 4300 / 2091 / 431 Регистрация: 19.07.2009 Сообщений: 3,162 Записей в блоге: 24
	10.06.2013, 14:52	3
	Судя по определению, обод — это простой цикл, то есть цикл без самопересечений. Проверить, является ли последовательность вершин циклом, не сложно: пары соседей должны быть соеденены и всё. Только обод, в отличии от цикла, как я понял, мыслится скорее как подграф, нежели как последовательность вершин. Хотя это вроде и не принципиально. Проверка подграфа на то, является ли он ободом, отличается от первой проверки тем, что вершины ещё нужно правильно упорядочить. Но это всё равно не сложно. Задача на нахождение всех ободов мне кажется очень интересной. Понятно, что любая точка — обод размера 1. Любое ребра — обод размера 2. Любой треугольник — обод размера 3. А дальше сложнее, потому что любой связной совокупности вершин можно сопоставить больше 1 обода, их всех обходящего, если ребер достаточно (см. Гамильтонов цикл в полном подграфе). Как решить такую задачу, кроме как полным переборам, я не знаю. 1

	10.06.2013, 15:35

Опции темы