Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/4: Рейтинг темы: голосов - 4, средняя оценка - 5.00
extrimally
7 / 7 / 2
Регистрация: 22.09.2012
Сообщений: 212
1

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

10.06.2013, 09:56. Просмотров 753. Ответов 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
Миниатюры
Является ли ободом последовательность вершин  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.06.2013, 09:56
Ответы с готовыми решениями:

Вводится последовательность из N вещественных чисел. Определить, является ли последовательность знакочередующе
Вводится последовательность из N вещественных чисел. Определить, является ли последовательность...

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

Вводиться последовательность из N целых чисел. Является ли последовательность убывающей?
Вводиться последовательность из N целых чисел. Является ли последовательность убывающей?

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

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

3
Igor3D
1229 / 596 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
10.06.2013, 12:20 2
Проблема с определением Прочитав (неск раз) я тоже не понимаю что значит "других ребер нет"? Если "вообще никаких нет", то ободом может являться только замкнутый контур, где каждая вершина имеет строго 2 ребра. Это явно глупо, напр задача "найти все ободы в графе" тогда не имела бы смысла - "граф или обод или нет".

Поэтому остается предположить что в ободе нет никаких других ребер связывающих любые 2 вершины V0..VN, и значит последовательность вершин 3-7-6-10-14-13-3 является ободом в данном графе
1
Mysterious Light
Эксперт по математике/физике
4094 / 2003 / 410
Регистрация: 19.07.2009
Сообщений: 3,022
Записей в блоге: 22
10.06.2013, 14:52 3
Судя по определению, обод — это простой цикл, то есть цикл без самопересечений.
Проверить, является ли последовательность вершин циклом, не сложно: пары соседей должны быть соеденены и всё. Только обод, в отличии от цикла, как я понял, мыслится скорее как подграф, нежели как последовательность вершин. Хотя это вроде и не принципиально.
Проверка подграфа на то, является ли он ободом, отличается от первой проверки тем, что вершины ещё нужно правильно упорядочить. Но это всё равно не сложно.

Задача на нахождение всех ободов мне кажется очень интересной. Понятно, что любая точка — обод размера 1. Любое ребра — обод размера 2. Любой треугольник — обод размера 3. А дальше сложнее, потому что любой связной совокупности вершин можно сопоставить больше 1 обода, их всех обходящего, если ребер достаточно (см. Гамильтонов цикл в полном подграфе). Как решить такую задачу, кроме как полным переборам, я не знаю.
1
extrimally
7 / 7 / 2
Регистрация: 22.09.2012
Сообщений: 212
10.06.2013, 15:35  [ТС] 4
Вчера начал писать код на C# для этой задачи - нахождение всех ободов. Я так и подумал про ободы. Но все-же у вас уточнил. Сейчас я почти закончил писать код
Цитата Сообщение от Mysterious Light Посмотреть сообщение
Понятно, что любая точка — обод размера 1. Любое ребра — обод размера 2. Любой треугольник — обод размера 3.
Обод – это граф, вершины которого V0,V1,…,Vn (n>=2) Значит минимум обод - это треугольник по определению.
в основе лежит Алгоритм поиска всех маршрутов между двумя заданными вершинами графа, то есть циклов. затем я вычислял где ободы. всем спасибо! вот код, если интересно:
Кликните здесь для просмотра всего текста
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
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 обода
0
10.06.2013, 15:35
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.06.2013, 15:35

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

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

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


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru