розглядаються завдання розпізнавання різних предфрактальних графів. Проведена математична постановка, розроблені ефективні алгоритми розпізнавання досліджуваних предфрактальних графів.

Анотація наукової статті з математики, автор наукової роботи - Кочкаров Расул Ахматович, Утакаева Ірина Хайрлиевна


ALGORITHMS OF RECOGNITION OF PREDFRACTAL GRAPHS WITH VARIOUS PRIMING

Problems of recognition of various predfractal graphs are considered. Mathematical statement is made, effective algorithms of recognition of investigated predfractal graphs are developed.


Область наук:
  • Математика
  • Рік видавництва: 2010
    Журнал: Известия Південного федерального університету. Технічні науки

    Наукова стаття на тему 'Алгоритми розпізнавання предфрактальних графів з різними затравки'

    Текст наукової роботи на тему «Алгоритми розпізнавання предфрактальних графів з різними затравки»

    ?Дагаєв Олександр Володимирович

    Технологічний інститут федерального державного освітнього закладу вищої професійної освіти «Південний федеральний» . .

    E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її..

    347928, м Таганрог, пров. Некрасовський, 44.

    Тел .: 88634371980.

    Бойченко Михайло Михайлович E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її..

    Тел .: 88634371980.

    Бородянський Юрій Михайлович E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її..

    .: 88634371787.

    Кафедра системного аналізу та телекомунікацій; доцент.

    Dagaev Aleksander Vladimirovich

    Taganrog Institute of Technology - Federal State-Owned Educational Establishment of Higher Vocational Education "Southern Federal University".

    E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її..

    44, Nekrasovskiy, Taganrog, 347928, Russia.

    Phone: 88634371980.

    Boichenko Mixail Mixailovich

    E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її..

    Phone: 88634371980.

    Borodyanskiy Juriy Mixaylovich

    E-mail: E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її..

    Phone: 88634371787.

    The Department of System Analysis and Telecommunications; associate professor.

    519.1

    P.A. Кочкаров, І.Х. Утакаева

    АЛГОРИТМИ РОЗПІЗНАВАННЯ ПРЕДФРАКТАЛЬНИХ ГРАФІВ З РІЗНИМИ затравки

    Розглядаються завдання розпізнавання різних предфрактальних графів. Проведена математична постановка, розроблені ефективні алгоритми розпізнавання досліджуваних предфрактальних графів.

    Граф; алгоритм; розпізнавання.

    R.A. Kochkarov, I.H. Utakaeva

    ALGORITHMS OF RECOGNITION OF PREDFRACTAL GRAPHS WITH

    VARIOUS PRIMING

    Problems of recognition of various predfractal graphs are considered. Mathematical statement is made, effective algorithms of recognition of investigated predfractal graphs are developed.

    Graph; algorithm; pattern recognition.

    Розпізнавання образів - чи не найпоширеніша завдання, яке людині доводиться вирішувати практично щомиті. Для цього людина використовує величезні ресурси свого мозку, включаючи одночасно близько 10 млрд нейронів. Саме це дає можливість людям миттєво дізнаватися один одного, читати

    тексти, керувати автомобілем. Завдання розпізнавання об'єктів і явищ є актуальним завданням штучного інтелекту і багатьох завдань у військовій області. На промислових підприємствах методи розпізнавання знайшли застосування при побудові систем технічної діагностики обладнання, розробці «інтелектуальних» роботів, в автоматизованих системах управління підприємствами. У сільському господарстві системи розпізнавання знаходять все більшого поширення не тільки в процедурах технічної діагностики техніки, але і при створенні сучасного технологічного обладнання. Методи і алгоритми розпізнавання все більшою мірою стають невід'ємним елементом медичної та

    , , локаційних систем спостереження, систем введення текстової, графічної та мовної інформації в ЕОМ [1].

    Розпізнавання являє собою задачу перетворення вхідної інфор-, ,

    , , , якого класу належить розпізнається образ, що дозволяє формалізувати по.

    , , запропонувати їх формулювання і можливі методи вирішення. Щоб в повному обсязі оцінити всі значення цієї проблеми, досить сказати, що створення штучного інтелекту - це побудова систем, що розпізнають, що наближаються за своїми можливостями до можливостей людини в рішенні задач распо- [1].

    Математичною моделлю багатьох завдань розпізнавання є задача розпізнавання предфрактального графа [2].

    Терміном «запал» домовимося називати будь-якої зв'язний П -вершина граф H = (Ж, Q), з непоміченими, тобто ненумерований вершинами і Е Ж .

    «», Операцію «заміщення вершини запалом» (ЗВЗ). Суть операції ЗВЗ полягає в заміщенні на кожному кроці кожної вершини Ук (к = 1..п) ЄУ графа О = (У, Е)

    п -вершина запалом Н, при цьому для кожного ребра, інцидентні з Ук,

    зазначена вершина замінюється на деяку вершину і з Ж .

    Визначимо поетапний процес виконання ЗВЗ. На етапі ? = 1 в даній затравки Н = (Ж, Q), нумеруем вершини і ребра, отриманий граф позначимо через О1 = (1, Е1).

    Нехай виконані етапи? = 1,2, ..., I, і по завершенню етапу I отриманий граф

    О, = (У ,, Е,), який називаємо предфроктальним (якщо I ^ ж, То мова будемо

    ).

    Нехай представлений в явному вигляді деякий граф, що володіє ознаками. -ются у відповіді на питання:

    1) чи є даний граф предфрактальним з певною запалом;

    2) ,

    побудує процес породження предфрактального графа з певною .

    Надалі будемо використовувати деякі необхідні ознаки пред-фрактальности графа О = (У, Е):

    a) для потужності безлічі вершин | У | = N існує непорожня множина пар п, Ь таких, що N = N (п, Ь);

    b) для потужності безлічі ребер | Е | існує хоча б одна пара п, Ь ,

    задовольняє рівності К1 = я (п, Ь);

    c) безліч ребер рангу Ь складається з об'єднання множин ребер запалів, що з'явилися в результаті того, що кожна вершина рангу Ь - 1 графа була заміщена запалом.

    У даній роботі досліджуються такі завдання:

    1. Нехай представлений в явному вигляді деякий граф О = (У, Е), що володіє всіма необхідними (але не є достатніми) ознаками предфрактального графа:

    a) для потужності безлічі вершин | у | = N існує пара п, Ь таких, що N = п1;

    b) для потужності безлічі ребер | Е | існує пара п, Ь, удовлетво-

    | 9 | п (п - 2) пь - 1

    ряющий рівності \ АЬ \ = ----------------;

    2 п - 1

    c) безліч вершин СКЛАДАЄТЬСЯ З двох підмножин У і В2, де У (У2) -

    безліч вершин V Е У ступеня? = П -1 (ступеня? = П - 2).

    Викладається відповідь на поставлене запитання з області теорії розпізнавання: чи є даний граф О = (У, Е) предфрактальним з непересічними «старими» ребрами [3], утвореним регулярної п -вершина запалом ступеня? = П - 2, за допомогою представленого нижче алгоритму.

    Опису алгоритму предпошлем лемму.

    Лемма 1. Нехай в предфрактальном графі О = (У, Е) дві вершини v1 і v2 належать одній затравки Н = (Ж, Q) (v1, v2 Е Ж) і мають суміжності з деякою вершиною V Е У, тоді v також належить цієї за.

    Доказ леми здійснюється міркуванням від противного:

    Дійсно, існування в предфрактальном графі О = (У, Е) двох вершин v1 і v2, що належать одній затравки Н = (Ж, Q) (^, v2 е Ж) І мають суміжності з деякою вершиною V Е У не своєю затравки, означає , що в траєкторії предфрактального графа О = (у, Е) деякий граф О, = ((,, Е,) містить кратні ребра, тобто є мультиграфом, що суперечить визначенню графа. Тоді вершина vеУ також належить цій затравки Н.

    алгоритм ах

    Опис процедури в- У безлічі У2 виділяється чергова неотмечен-

    *

    ная вершина v1, тобто вершина, яка не належить будь-якої вже виділеної затравки. Вершина V1 Е У2 має ступінь п - 2, тобто суміжно з п - 2 новими вершинами своєї затравки Н = (Ж, Q), які позначаються через vk, де

    к = 2, п - 1 і фарбуються. В результаті маємо п - 1 виділених вершин п - , . . . -

    рим тепер вершини V Е У, суміжні з виділеними vk, к = 1, п - 1, але нефарбовані, і виділимо серед них вершину Vn, яка буде мати суміжності з п - 2 з вже пофарбованих п - 1 вершин. Згідно лемі 1, вершина Vn також буде належати затравки Н = (, Q). Через Ж 'позначаємо безліч всіх вершин, зазначених процедурою в. Якщо потужність | Ж '| = П, то виділяємо і фарбуємо все ребра, у кожного з яких кінці являють собою вершини даного безлічі Ж '. Робота процедури в завершується перевіркою: чи утворює безліч виділених таким чином вершин і ребер п -вершина зв'язний однорідний граф степеня? = П - 2. Якщо так, то крок, який включає в себе описану процедуру в, завершується результативно і слід перехід до наступного кроку першого етапу. В іншому випадку, крок вважається безрезультатним і алгоритм а припиняє свою роботу.

    Наведемо обчислювальну схему першого етапу в разі, коли на його вхід представлений вихідний граф О = (У, Е).

    Етап р = 1 починає свою роботу з перевірки виконання рівності | у | = Пь. Якщо це рівність не виконується, то алгоритм а! закінчує роботу з певним результатом: «представлений граф О = (У, Е) не є предфрак-тальний з непересічними« старими »ребрами, утвореним регулярної п -вершина запалом ступеня? = П - 2.

    , Про У1 ,

    що складається з вершин ступеня? = П - 1, і У2, що складається з вершин ступеня? = П - 2. Якщо різниця У \ (і У2) Ф в, то алгоритм закінчує роботу безру-

    . , У 1 У2 У ,

    подальша робота етапу р = 1 складається з т0 кроків, де т0 - число таких затра-, .

    Результатом кожного такого кроку є виділена в графі Про чергова запал. Процедуру виділення цієї затравки позначимо через у.

    Етап р = 1 завершується, коли в даному графі О = (У, Е) всі вершини

    У .

    Після закінчення першої частини алгоритму а! здійснюємо перевірку, чи всі вершини вихідного графа Про виявилися зазначеними. Якщо так, то перший етап алгоритму а! закінчує свою роботу наступною процедурою. вихідний граф

    Про позначається через О * і представляється в якості першого члена послідовності про **, О * -1, ..., О *. Кожна виділена запал графа Про стягується в одну .

    Про * -1. Далі, по відношенню до нього реалізуємо черговий етап алгоритму.

    Послідовне застосування алгоритму до свого попереднього результату породжує послідовність графів О1 = (, Е1), I =, яка в разі ус-

    пешню роботи кожного застосування алгоритму являє собою траєкторію, записану в зворотному порядку О *, О * -1, ..., О1 *.

    Принципова распознаваемость предфрактального графа О = (V, Евитекает з конструктивного опису алгоритму. Природне запитання, що виникає після результативного процесу розпізнавання, полягає в наступному: якщо отриману послідовність О *, О * -1, ..., О1 * записати в зворотному порядку, то чи має місце збіг цього запису з траєкторією, яка нам не відома (бо інакше не був би питання розпізнавання)? Відповідь на це питання можна вважати позитивним в тому випадку, коли при побудові цієї послідовності ніколи не виникала альтернативність при виділенні кожної затравки. Відсутність альтернативності в зазначеному сенсі будемо називати терміном «однозначність результатів роботи» даного алгоритму розпізнавання.

    Розглянемо питання про обчислювальної складності алгоритму а1 і зробимо

    оцінку трудомісткості алгоритму т (а1). У процесі реалізації етапів алгоритму здійснюються такі операції: визначення ступеня вершини, виявлення околиці радіуса 1 для цієї вершини, перегляд всіх пар вершин графа на,. виконуються в межах однієї затравки, то верхня оцінка етапу не перевищує сукупну кількість ребер, виділених та зазначених в процесі роботи етапу. Звідси, справедлива

    Теорема 1. Будь-предфрактальний граф О * = (V *, ЕЬ) з регулярною запалом н = {ж, 0), Щ = п, deg ^ = п - 2, ^ ещ розпізнається алгоритмом ОСГ, якщо «старі» ребра не перетинаються , з обчислювальної трудомісткістю алгоритму т (а1) < 0 (е | ь) .

    2. ,

    О = (, Е), що володіє наступними необхідними ознаками

    :

    а) для потужності безлічі вершин | ^ | = N існує пара п, Ь така, що

    КІ =

    п2 (п +1) 2, при Ь - парному,

    Ь + 1 Ь-1

    п 2 (п +1) 2, при Ь - непарному;

    Ь

    Ь

    Ь) для потужності безлічі ребер | Е | існує пара п, Ь, яка задовольнить рівності

    N =

    I 2 (п + 1) 2 - 1

    (+ Q2п) ------------------------, при Ь -четном,

    п (п + 1) - 1

    Ь-1 Ь-1

    , ч п 2 (п +1) 2 -1 ^ Т

    (+ Q2п) - + п 2 (п + 1) 2 q1, при Ь - непарному,

    п (п + 1) - 1

    п (п + 1) (п + 1) (п + 2)

    де а, = --------; 2 =------------.

    2 + 2

    с) безліч вершин СКЛАДАЄТЬСЯ З двох підмножин V І У2, де V (У2) - безліч вершин V е У ступеня V = п +1 (ступеня V = п).

    Тут викладається відповідь на поставлене запитання: чи є представлений граф G = (У, Е) предфрактальним графом з непересічними ^^^ ими »ребрами, утвореним двома повними затравки I 1 = (Ж1, Q1) і / 2 = (Ж2, Q2) , де потужності вершин | ^ | = П, | Ж2 | = П +1. Процедура заміщення вершини запалом (ЗВЗ) [2] проводиться на непарних номерах етапів Ь запалом

    I 1 = (Ж1, Q1) і запалом I 2 = (Ж2, Q2) на парних номерах етапів.

    Для розпізнавання предфрактального графа G = (У, Е) побудований алгоритм А2.

    алгоритм а2

    Процедуру виділення затравки Н1 = (Ж1, Q1) (H2 = (Ж2, Q2)) позначимо через Д (В2). , -

    змінювати ту чи іншу процедуру: якщо довжина траєкторії заданого предфрактального графа Ь - парна, то на останньому кроці було заміщення запалом Нг = (Ж1, Q1), тому на першому етапі слід скористатися процедурою Д, в іншому випадку - процедурою д. На наступних етапах процедури будуть .

    Опис процедури вх (виділення затравки Н1 = (Ж1, Q1)) | Виділяємо в безлічі У чергову невідзначеними вершину v1 е У [1,2]. Якщо v1 е У2, то deg v1 = п, тобто v1 суміжно з (п - 1) новими вершинами своєї затравки. Розглянемо вершини, суміжні з виділеної vk, к = 2, п +1, але нефарбовані, і,. 1, ці вершини також належатимуть затравки. У разі, коли V * е У1, то deg V * = n +1, тобто суміжно з (п - 1) новими вершинами своєї затравки. рассмот-

    * -Р г \ г \

    рим тепер вершини, суміжні з виділеної vk, к = 2, п + 2, але незабарвлені,

    і виділимо серед них ті, які матимуть суміжність між собою, відповідно до леми 1, ці вершини також буде належати затравки. Через Ж 'позначаємо безліч всіх вершин, зазначених процедурою в1. Якщо ПОТУЖНІСТЬ Ж '| = П, то виділяємо і фарбуємо все ребра, у кожного з яких кінці представляють зі-

    Ь

    бій вершини даного безлічі Ж '. Робота процедури Д завершується перевіркою: чи утворює безліч виділених таким чином вершин і ребер п -вершина повний граф. Якщо так, то крок, який включає в себе описану процедуру Д, завершується результативно, і слід перехід до наступного кроку. ,, А припиняє свою роботу.

    Опис процедури В2 (виділення затравки Н2 = (Ж2, Q2)). Виділяємо в безлічі V чергову невідзначеними вершину v1 Е V. В разі, коли

    V Е V2, то yoед V * = п, тобто У1 суміжно з п новими вершинами своєї затравки, які позначаємо через vk, де к = 2, п +1 і фарбуємо. Якщо ж V Е V1, то yoе§V * = n +1, тобто v1 суміжно з п новими вершинами своєї затравки. рас-

    до

    дивимося ті вершини, які суміжні з виділеної vk, к = 2, п + 2, але НЕОК,,. 1, .

    Ж позначаємо безліч всіх вершин, зазначених процедурою В2. Якщо потужність Ж 'I = п +1, то виділяємо і фарбуємо все ребра, у кожного з яких кінці являють собою вершини даного безлічі Ж'. Робота процедури В2: -шин і ребер (п + 1) -вершина повний граф. Якщо так, то крок, який включає в себе описану процедуру рг, завершується результативно, і слід перехід до наступного кроку першого етапу. В іншому випадку, крок вважається безрезультатним, і алгоритм а1 припиняє свою роботу.

    Етап р = 1 починає свою роботу з перевірки виконання рівності

    п 2 (п + 1) 2, при Ь - парному ,

    Ь + 1 Ь-1

    п 2 (п +1) 2, при Ь - непарному .

    Якщо рівність не виконується, то алгоритм А2 закінчує роботу безрезультатно. В іншому випадку, в графі Про виділяються безлічі У1, що складається з вершин ступеня п + 1, і У2, що складається з вершин ступеня п. якщо різниця

    V \ (і У2) Ф в, то алгоритм закінчує роботу з негативним результатом, в тому сенсі, що даний граф не є предфрактальним графом з непересе-каються «старими» ребрами, утвореним двома повними затравки

    І 1 = №х, Q1) і I 2 = (Ж2,02), де потужності вершин | ^ | = П, \ Ж2 \ = п +1, в якому процедура заміщення вершини запалом (ЗВЗ) [2] проводиться на непарних етапах запалом I 1 = (Ж1, Q1), а на парних Ї 2 = (Ж2, Q2). В іншому випадку,

    У і В2 утворюють розбиття множини V, і подальша робота етапу р = 1 складається з т0 кроків, де т0 - число таких запалів, кожна з яких складається з

    нових ребер. Результатом кожного такого кроку є виділена в графі Про

    чергова запал.

    У разі результативної роботи кожного з Ь -1 етапів в якості останнього члена послідовності отримаємо п -вершина повний граф. Цей результат означає отримання позитивної відповіді на питання: чи є представлений граф предфрактальним графом з непересічними «старими» ребрами, утвореним двома повними затравки I 1 = (Ж1, Q1) і I 2 = (Ж2, Q2), де потужності вершин ^ 1 = п, | Ж2 \ = п +1, де процедура заміщення вершини запалом (ЗВЗ) проводиться на непарних етапах запалом I х = (Ж1, Q1), а на парних

    кає з конструктивного опису алгоритму. Якщо отриману послідовність О *, ОЬ-1, ..., О1 * записати в зворотному порядку, то чи має місце збіг цього запису з траєкторією? Відповідь на це питання можна вважати позитивним в

    ,

    альтернативність при виділенні кожної затравки.

    Розглянемо питання про обчислювальної складності алгоритму А2. В процесі

    реалізації етапів алгоритму А2 здійснюються такі елементарні операції: визначення ступеня вершини, виявлення околиці радіуса 1 для цієї , ,

    . -, , виділених та зазначених в процесі роботи етапу. Звідси справедлива

    Теорема 2. Будь-який предфрактальний граф ОЬ = (V *, ЕЬ), утворений двома повними чергуються затравки Н1 = (Ш1, Q1) і Н2 = (Ж2, Q2), розпізнається алгоритмом А2, якщо «старі» ребра не перетинаються з обчислювальної трудомісткістю алгоритму т (а2)< про (е | ь)-

    3. Нехай заданий в явному вигляді деякий граф О = (У, Е), що володіє необхідними ознаками предфрактального графа:

    а) для потужності безлічі вершин V = N існують п, т, Ь такі, що

    вите-

    ,при Ь - парному;

    Ь) ДЛЯ ПОТУЖНОСТІ безлічі ребер | Е існують п, т, Ь, удовлетво-:

    т 2 п 2, при Ь - непарному ,

    Ь +1 Ь -1

    до

    с) безліч вершин СКЛАДАЄТЬСЯ З двох підмножин V І У2, де У1 (У2)-безліч вершин V е V ступеня V = п +1 (ступеня deg V = п). Представлений відповідь на питання: чи є представлений граф О = (V, Е) предфрактальним графом О = (V, Е) з двома повними затравки I х = (Ж1, Q1) і I 2 = (Ж2, Q2), де потужності множин вершин | ^ 1 | = Т і | ^ 2 | = П, в разі, коли суміжність старих ребер не порушується. Причому процедура ЗВЗ проведена на непарних етапах запалом I х = (Ж1, Q1), і I 2 = (Ж2 ^ 2) на парних.

    Для розпізнавання описаного предфрактального графа О = (V, Е) розроблений алгоритм а3.

    алгоритм а3

    Процедура виділення затравки I 1 = (Ж1, Q1) і I 2 = (Ж2, Q2) позначається ^ (ТГ) в разі, якщо довжина траєкторії О = (V, Е) Ь - непарна (парна), то на останньому кроці було заміщення запалом I 1 = (^ 1, Q1) (I 2 = (Ж2, Q2)). Отже, для предфрактального графа непарного рангу Ь слід скористатися процедурою У \, в іншому випадку - процедурою у2. На наступних етапах процедури будуть чергуватися.

    Опис процедури (виділення затравки Нх = (ЖГ, Q1)). у множе-

    стве V виділяється чергова невідзначеними вершина V. Так як будь-яка «нова» запал Нх = (ЖГ, Q1) має т - 1 вершину ступеня т - 1 і одну вершину, ступінь якої більше, ніж т - 1, то Vv е V ^^ шожни два випадки:

    1. degv = т - 1;

    2. degv > т - 1.

    У першому випадку вихідна вершина і суміжні з нею т - 1 вершин об'єд-

    т (т - 1)

    ють у безліч. Далі фарбуються всі вершини, а також--------------------

    ребер, кінці яких належать .

    У другому випадку розглянута вершина V має інциденти нтность не тільки з (ш - 1) «новим» ребром, а й зі «старими» ребрами. Серед безлічі вершин, суміжних з V, виділяються т - 1 вершин, ступінь яких т - 1. Вихідну вершину V і виділені т - 1 вершин ступеня т - 1 об'єднують у мно-

    Т17 т (т - 1)

    дружність "1. Після чого фарбуються вершини" 1, а також ------------- ---- ребер,

    "1 .

    Робота процедури Уг завершується перевіркою: чи утворює безліч виділених таким чином вершин і ребер ш-верховий повний граф. Якщо так, то крок, який включає в себе описану процедуру Уг, завершується результативно, і слід перехід до наступного кроку першого етапу. В іншому випадку, крок вва-

    ,

    відповіддю на поставлене запитання розпізнавання: Чи є представлений

    граф G = (, Е) предфрактальним графом G = (V, Е) з двома повними затравки Ї 1 = (Ж ,, Q1) і I 2 = (Ж2,02), де ПОТУЖНОСТІ множин вершин 1 ^ 1 = т "щ = п, в разі, коли суміжність старих ребер не порушується, де процедура ЗВЗ проведена на непарних номерах етапів запалом I, = (Ж1, Q1) і запалом / 2 = (Ж2, Q2) на парних? »

    Опис процедури у2 (виділення затравки Н2 = (Ж2, Q2)). у безлічі

    V виділяється чергова невідзначеними вершина V. Так як будь-яка «нова» запал Н2 = (Ж2, Q2) має п -1 вершину ступеня п - 1 і одну вершину, ступінь якої більше п - 1, то Vv Є V можливі два випадки:

    1. degv = п - 1;

    2. degv > п - 1.

    У першому випадку вихідна вершина і суміжні з нею п - 1 вершин об'єднуються в безліч '2. Далі фарбуються вершини '2, а також -1)

    ребер, кінці яких є вершини Ж2 .

    У другому випадку, вершина V має инцидентность не тільки з п - 1 «новим» ребром, а й зі «старими» ребрами. Серед вершин, суміжних з V, виділяють п - 1 вершин зі ступенем п - 1. Вихідну вершину V і виділені п - 1 вершини ступеня п - 1 об'єднують в безліч Ж2. Далі фарбуються вершини Ж2, а також п - (- 1) ребер, кінці яких є вершини

    2

    '2 .

    Робота процедури у2 завершується перевіркою: чи утворює безліч виділених таким чином вершин і ребер п -вершина повний граф. Якщо так, то крок, який включає в себе описану процедуру у2, завершується результативно, і слід перехід до наступного кроку першого етапу. В іншому випадку, крок вва-

    ,

    відповіддю на поставлене запитання розпізнавання: Чи є представлений граф G = (V, Е) предфрактальним графом G = (V, Е) з двома повними затравки I 1 = (Ж1, Q1) і I 2 = (Ж2, Q2), де потужності множин вершин | ЖХ | = Т і | Ж21 = п, в разі, коли суміжність старих ребер не порушується, де процедура ЗВЗ проведена на непарних етапах запалом I 1 = (Ж1, Q1), і I 2 = (Ж2, Q2)? »

    Після закінчення першої частини описаних вище алгоритмів, здійснюється перевірка: чи всі вершини вихідного графа виявилися зазначеними. Якщо так, то перший етап алгоритмів закінчує свою роботу наступною процедурою. Вихідний граф позначається через G, L і представляється в якості першого члена по-

    G * / ' "' Г * / ~ 1 * т /»

    Ь, GL -1, ..., G1. Кожна виділена запал стягується в

    вершину. Отриманий в результаті стягування граф позначається через GL-1.

    , , .

    У разі результативної роботи кожного з L -1 етапів в якості останнього члена послідовності отримаємо m -вершина повний граф. Цей результат означає отримання позитивної відповіді на питання: чи є представлений граф предфрактальним графом з непересічними «старими» ребрами, утвореним двома повними затравки I 1 = (W1, Q1) і I 2 = (W2, Q2), де потужності вершин W \ = m, | W2 | = N, де процедура ЗВЗ проводиться на непарних етапах запалом I 1 = (W1, Q1), а на парних I 2 = (W2, Q2).

    Принципова распознаваемость досліджуваного предфрактального графа G = (V, E) випливає з конструктивного опису алгоритму а3 і однозначності результатів його роботи.

    Розглянемо питання про обчислювальної складності алгоритму ОС3. У процесі реалізації етапів алгоритму здійснюються такі операції: визначення, 1, всіх пар вершин графа на предмет суміжності, виділення і фарбування ребер. Так як ці операції виконуються в межах однієї затравки, то верхня оцінка етапу не перевищує сукупну кількість ребер, виділених та зазначених в процесі роботи етапу. Звідси, справедлива

    Теорема 3. Всякий предфрактальний граф GL = (VL, EL) з двома повними затравки розпізнається алгоритмом а3, де суміжність старих ребер не порушується з обчислювальної трудомісткістю алгоритму т (а3) < o (e | L).

    БІБЛІОГРАФІЧНИЙ СПИСОК

    1. Горелик А.Л., Скрипкін В.А. Методи розпізнавання. - М., 2004.

    2. Ємеля ічев В А. і ін. Лекції з теорії графів. - М., 1990..

    3.. . : . - -

    ний Архиз, 1998..

    4.. ,. -., 2004.

    5. Шредер М. Фрактали, хаос, статечні закони. - М., 2005.

    6. Мандельброт Б. Фрактальна геометрія природи. -, 2002.

    Кочкаров Расул Ахматович

    Фінансова академія при уряді РФ.

    E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її. 125993, Москва, Ленінградський просп., 49.

    Тел .: 88782202387.

    Кафедра математичного моделювання та динамічних процесів; докторант. Утакаева Ірина Хайрлиевна

    Карачаєво-Черкеська державна технологічна академія.

    E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

    125993, Москва, Ленінградський просп., 49.

    .: 88782202387.

    Кафедра математики; асистент.

    Kochkarov Rasul Ahmatovich

    Financial academy of Russian Federation.

    E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її. 125993, Moscow, Leningrad Ave., 49.

    Phone: 88782202387.

    The Department of mathematical modeling and dynamic processes; candidate for a doctor's.

    Utakaeva Irina Hairlyevna

    Karachai-Cherkess State technological academy.

    E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

    49, Leningrad Ave., Moscow, 125993, Russia.

    Phone: 88782202387.

    The Department of mathematic; assistant.

    УДК 621.311.1.016.312

    . . , . .

    Про оцінку ЯКОСТІ ЕЛЕКТРОЕНЕРГІЇ

    Аналіз і скорочення втрат трифазної електроенергії.

    електроенергія; аналіз і скорочення втрат трифазної електроенергії.

    B.A. Gusev, J.V. Pahomov ABOUT QUALITY OF ELECTRICAL ENERGY

    Analysis and shorten of waste three-phase electrical energy.

    Electrical energy; analysis and shorten of waste three-phase electrical energy.

    В однофазної системі повна потужність W визначається з урахуванням діючого значення струму I, що протікає через навантаження, і діючого значення напруги U на її клемах по

    W = UI = (P2 + Q2) 1/2, (1)

    де P і Q - активна і реактивна потужності навантаження, при цьому передбачається, U I .

    W, U,

    допустимо оцінити по сумі алгебри фазних потужностей WA, WB і Wc по

    W.i = Wa + Wb + Wc = U (Ia + Ib + Ic). (2)

    На практиці для оцінки споживання енергії застосовується геометрична повна потужність Wre0M, яка визначається виразом

    W2reoM = p2 + Q2 = (P A + P B + P C) 2+ (QA + QB + QC). (3)

    Дійсна ж повна потужність Wa

    ^ Д = (і 2 A + U2 B + U2 C) (I2A + I2B + I2C). (4)

    Неоднозначність визначення W в трифазній спотворює системі, в част, U, UA, UB

    UC, W G ( -

    водимо між проводами), яка виражається рівнянням [1]

    T

    APu = (G / T) x ^ (ua + Ub + Uc) dt. (5)

    0


    Ключові слова: ГРАФ / АЛГОРИТМ / РОЗПІЗНАВАННЯ / GRAPH / ALGORITHM / PATTERN RECOGNITION

    Завантажити оригінал статті:

    Завантажити