Alexandr Gavrikov

Primenenie teorii grafow dlq zadach otkazoustojchiwosti

• Broschiertes Buch

Produktbeschreibung

T-neprivodimye rasshireniya yavlyajutsya odnim iz vidov optimal'nyh rasshirenij dlya orgrafov. Konstrukcii optimal'nyh rasshirenij primenyajutsya v diagnostike diskretnyh sistem i kriptografii, a takzhe v zadachah otkazoustojchivosti. V obshhem sluchae zadacha opredeleniya togo, yavlyaetsya li orgraf H rasshireniem dlya orgrafa G, yavlyaetsya NP-polnoj, a zadacha poiska TNR po zadannomu orgrafu G ne prinadlezhit klassu NP. V knige opisany polinomial'nyj algoritm postroeniya dlya cepi otlichnogo ot kontura TNR, polinomial'nyj algoritm postroeniya dlya zvezdy razlichnyh neizomorfnyh drug drugu TNR i polinomil'nyj algoritm postroeniya dlya zvezdy minimal'nogo TNR. Takzhe dokazany teorema o postroenii odnogo iz TNR dlya objedineniya cepej i opisan polinomial'nyj algoritm postroeniya minimal'nogo TNR dlya objedineniya cepej. Vse predlozhennye algoritmy imejut dokazatel'stvo korrektnosti. Issledovany TNR dlya mnogougol'nyh orgrafov. Dokazana teorema o postroenii odnogo iz TNR dlya mnogougol'nyh orgrafov s chetnym kolichestvom vershin. Poluchen polinomial'nyj algoritm postroeniya TNR dlya proizvol'nogo mnogougol'nogo orgrafa. Dokazana teorema o korrektnosti predlozhennogo algoritma.

Produktdetails

• Verlag: LAP Lambert Academic Publishing
• Seitenzahl: 64
• Erscheinungstermin: 29. Mai 2017
• Russisch
• Abmessung: 220mm x 150mm x 4mm
• Gewicht: 113g
• ISBN-13: 9783330090019
• ISBN-10: 3330090014
• Artikelnr.: 48550421

Autorenporträt

Zakonchil Saratowskoj gosudarstwennyj uniwersitet i aspiranturu tam zhe po special'nosti "Diskretnaq matematika i matematicheskaq kibernetika". Na dannyj moment qwlqetsq razrabotchikom w OOO "Yandex. Market Lab". Sfera nauchnyh interesow - algoritmy na grafah.