Հայաստանի ատենախոսությունների բաց մատչելիության պահոց = Open Access Repository of the Armenian Electronic Theses and Dissertations (Armenian ETD-OA) = Репозиторий диссертаций Армении открытого доступа

Անկախության թվի հետազոտումը ընդհանրացված ցիկլերի ուժեղ արտադրյալի համար

Բադալյան, Սևակ Հարությունի (2012) Անկախության թվի հետազոտումը ընդհանրացված ցիկլերի ուժեղ արտադրյալի համար. PhD thesis, ԵՊՀ.

[img]
Preview
PDF (Abstract)
Available under License Creative Commons Attribution.

Download (563Kb) | Preview

    Abstract

    Գրաֆների ուժեղ արտադրյալի անկախության թվերի ուսումնասիրությունը սկիզբ է առել 1956 թվականին, երբ Կլաուդ Շենոնի կողմից դրվեց ինֆորմացիայի տեսության հիմնարար խնդիրներից մեկը` անսխալ կապուղու թողունակությունը գտնելու խնդիրը: Ինֆորմացիայի կապուղու թողունակությունը արտահայտվում է դրա բնութագրիչ գրաֆի ուժեղ արտադրյալով աստիճանների անկախության թվերի միջոցով: Գրաֆի Շենոնի թողունակությունը գտնելու խնդիրը ունենալով մեծ կիրառական նշանակություն ինֆորմացիայի տեսությունում, համարվում է բարդ խնդիր և մինչ այժմ այն լուծված չէ այնպիսի պարզ գրաֆի համար, ինչպիսին, օրինակ 7 գագաթանի պարզ ցիկլն է: Շենոնի խնդրից է սկիզբ առել նաև կատարյալ գրաֆների տեսությունը: Կատարյալ գրաֆները պատկանում են գրաֆների այն փոքրաթիվ դասերից մեկին, որի համար Շենոնի թողունակությունը հայտնի է: Գրաֆի Շենոնի թողունակության բացահայտ արժեքը գտնելու խնդիրը լինելով չափազանց բարդ խնդիր, արվել են նրա համար ստորին և վերին գնահատականներ ստանալու բազմաթիվ փորձեր: Ստորին գնահատականներ ստանալու հիմնական եղանակը գրաֆների ուժեղ արտադրյալով աստիճանների անկախության թվերը որոշելն է: 1971 թվականին Ա. Գ. Մարկոսյանի և ավելի ուշ Ռ.Ս. Հալեսի և այլոց կողմից հաշվվեց կամայական երկու պարզ ցիկլերի ուժեղ արտադրյալի անկախության թիվը: Այնուհետև, տարբեր աշխատանքներում ստացվեցին որոշակի գնահատականներ ցիկլերի բարձր աստիճանների անկախության թվերի համար: 1979 թվականին Լովասի կողմից հաջողվեց նշանակալի առաջընթաց արձանագրել գրաֆի Շենոնի թողունակությունը գտնելու խնդրում: Նա ներմուծեց գրաֆի նոր ինվարիանտ` գրաֆի Լովասի թիվը, որը հանդիսանում է բավականին հաջող վերին գնահատական Շենոնի թողունակության համար: Լովասի թիվը 5 գագաթանի պարզ ցիկլի համար համընկավ վերը նշված ստորին գնահատականի հետ և հնարավորություն տվեց գտնելու երկար ժամանակ անհայտ 5 գագաթանի ցիկլի Շենոնի թողունակությունը: Գրաֆների և մասնավորապես ցիկլերի Շենոնի թողունակության համար ավելի լավ ստորին և վերին գնահատականներ ստանալու բազմաթիվ փորձեր են արվում: Այսպես, 2000 թվականին Վեսելի և Զեռովնիկի կողմից համակարգչային փնտրման միջոցով 7 գագաթանի ցիկլի 4-րդ աստիճանի գրաֆում գտնվեց 108 գագաթանի անկախ բազմություն, որը հնարավորություն տվեց լավացնելու Շենոնի թողունակության ստորին գնահատականը 7 գագաթանի ցիկլի համար, 2007 թվականին Բրիմկովի կողմից բացահայտ բանաձևով տրվեց որոշ ցիրկուլանտ գրաֆների Լովասի թիվը և այլն: В 1956 г., С. Шеннон сформулировал одну из фундаментальных проблем теории информации - нахождение пропускной способности шумного канала [см. “C. E. Shannon, The zero-error capacity of a noisy channel, Transactions on Information Theory, Inst. Radio Eng., IT-2, 1956, pp. 8-19”]. Проблема оказалась тесно связанной с числами независимости сильного произведения графов. пропускная способность графа определяется следующим образом: где - число независимости n-ой степени графа (определенной сильным произведением графов). Пропускная способность шумного канала выражается пропускной способностью графа соответствующего этому каналу. Проблема нахождения пропускной способности графа сложна и известны всего лишь несколько классов графов для которых определение пропускной способности не представляет трудности (например универсальные графы). Проблема сложна даже для таких простых графов как нечетные циклы. Пропускная способность была неизвестна около 20 лет до того, как Л.Ловас оригинальным подходом доказал и ввел число Ловаса – достаточно хорошая верхняя граница для [see “L. Lovasz, On the Shannon capacity of a graph, IEEE Transactions on Information Theory, IT-25, 1979, pp. 1-7”]. Так как определение значения является достаточно сложным, различные верхние и нижние границы были найдены для. Следующие результаты получены Розенфельдом [see “M. Rosenfeld, On a problem of C. E. Shannon in graph theory, Proc. Amer. Math. Soc., 18, 1967, pp. 315-319”] для чисел независимости и покрытия графов и: где - число Розенфельда графа (или дробное число независимости). Позднее Маркосян [см. “А. Г. Маркосян, Число внутренней устойчивости в декартовом произведении простых циклов, Известия Академии Наук Армянской ССР, Серия Математика 6:5, 1971, стр. 386-392”] и Халес [см. “R. S. Hales, Numerical Invariants and the Strong Product of Graphs, Combinatorial Theory (B), 15, 1973, pp. 146-155”] показали что для циклов имеют место равенства (в неравенствах выше). In 1956, C. Shannon formulated one of the fundamental problems in information theory, finding the capacity of a noisy channel [see “C. E. Shannon, The zero-error capacity of a noisy channel, Transactions on Information Theory, Inst. Radio Eng., IT-2, 1956, pp. 8-19”]. The problem proved to be tightly connected with the problem of finding independence numbers of the strong products of graphs. Shannon capacity of a graph is defined as follows: where is the independence number of the n-th degree of (defined through the strong product of graphs). Capacity of a noisy channel is expressed through the Shannon capacity of a graph corresponding to the channel. The problem of finding the Shannon capacity of a graph is a difficult problem and there are only few classes of graphs with known capacities (e.g. universal graphs). The problem is difficult even for such simple graphs as odd cycles. was unknown for about 20 years until L. Lovasz proved with an original approach and introduced the Lovasz number of a graph, an upper bound for [see “L. Lovasz, On the Shannon capacity of a graph, IEEE Transactions on Information Theory, IT-25, 1979, pp. 1-7”]. Different lower and upper bounds have been found for taking into account that finding the explicit value of is quite difficult. The following results were obtained by Rosenfeld [see “M. Rosenfeld, On a problem of C. E. Shannon in graph theory, Proc. Amer. Math. Soc., 18, 1967, pp. 315-319”] for the independence and clique covering numbers of any and graphs: where is the Rosenfeld number of a graph (or otherwise known as fractional independence number). Later Markosyan [see “А. Г. Маркосян, Число внутренней устойчивости в декартовом произведении простых циклов, Известия Академии Наук Армянской ССР, Серия Математика 6:5, 1971, стр. 386-392”] and Hales [see “R. S. Hales, Numerical Invariants and the Strong Product of Graphs, Combinatorial Theory (B), 15, 1973, pp. 146-155”] showed that for cycles equality takes place (in inequalities above).

    Item Type: Thesis (PhD)
    Additional Information: О числе независимости сильного произведения обобщенных циклов. On the independence number of the strong product of generalized cycles
    Uncontrolled Keywords: Бадалян Севак Арутюнович,Badalyan Sevak
    Subjects: Physics
    Divisions: UNSPECIFIED
    Depositing User: NLA Circ. Dpt.
    Date Deposited: 01 Dec 2015 13:11
    Last Modified: 13 Mar 2017 16:08
    URI: http://etd.asj-oa.am/id/eprint/77

    Actions (login required)

    View Item