Кіріспе

Графтардағы циклдарды бұзу үшін алынып тасталатын ең аз жиектер саны. Бағытталған графтардағы циклдік ранг деп аталатын туыс ұғым. Граф теориясында, математиканың бір саласы, бағытталмаған графтың контурлық рангі, цикломатикалық саны, циклдік рангі немесе нөлдігі – бұл графтың барлық циклдарын бұзып, оны ағаш немесе орманға айналдыру үшін графтан алынып тасталуы тиіс жиектердің ең аз саны. Ол графтың тәуелсіз циклдарының санына тең (циклдік негіздің өлшемі). Бағытталған графтар үшін сәйкес келетін кері байланыс доғалары жиынының мәселесінен айырмашылығы, контурдың r-рангісі келесі формула арқылы оңай есептеледі: , мұнда m – берілген графтың жиектерінің саны, n – төбелердің саны, ал c – байланысқан компоненттердің саны. Сондай-ақ, барлық циклдарды тиімді түрде бұзатын ең аз жиектер жиынтығын ашкөз алгоритмді қолдану немесе жаппай орманды толықтыру арқылы құруға болады. Контурлық рангі алгебралық граф теориясы тұрғысынан графтың циклдық кеңістігінің өлшемі ретінде, матроид теориясы тұрғысынан графикалық матроидтың корангі ретінде және топология тұрғысынан графтан туындаған топологиялық кеңістіктің Бетти сандарының бірі ретінде түсіндірілуі мүмкін. Ол графтың құлақтық ыдырауындағы құлақтарды санайды, шамамен ағаштардағы параметрленген күрделіліктің негізін құрайды және бағдарламалық қамтамасыз ету метрикасында кодтың цикломатикалық күрделілігін анықтаудың бір бөлігі ретінде қолданылады. Бұл ұғымды «цикломатикалық сан» деген атаумен Густав Кирхгофф енгізген.

Матроидтық дәреже және минималды кері байланыс шеті жиынтығының құрылысы

G графигінің контурлық рангі матроид теориясын қолдана отырып, G графигінің графикалық матроидының коранкі ретінде сипаттауға болады. Матроидтардың ашкөз қасиетін пайдалану арқасында, қалған графтың кем дегенде бір циклына жататын шетті әр қадамда таңдайтын ашкөз алгоритмді қолданып, барлық циклдарды жоятын шеттердің ең кіші жиынтығын табуға болады. Балама ретінде, G-нің жапсарлас орманды құрастырып және осы жапсарлас орманға кірмейтін шеттердің толықтыру жиынтығын таңдау арқылы барлық циклдарды жоятын шеттердің ең кіші жиынтығын табуға болады.

Тәуелсіз циклдердің саны

Алгебралық графтар теориясында контурлық дәреже – цикл кеңістігінің өлшемі болып табылады. Бұл, контурлық дәреже графиктегі тәуелсіз циклдардың санын есептейді деп түсіндіруге болады, мұнда циклдар жиыны тәуелсіз болып есептеледі, егер олардың біреуін қалғандарының бір бөлігінің симметриялық айырмасы ретінде құру мүмкін болмаса. Осы топологиялық байланысқа байланысты, G графигінің цикломатикалық саны G графигінің бірінші Бетти саны деп те аталады. Кез келген топологиялық кеңістіктің бірінші Бетти саны да дәл осылай анықталады және кеңістіктегі тәуелсіз циклдардың санын есептейді.

Желілік коэффициент

Жазық графиктер үшін контурлық рангтың бір түрі, сол түбірлі жиынға жататын кез келген жазық графиктің ең жоғары мүмкін контурлық рангіне бөлу арқылы нормалданады, және бұл торлылық коэффициенті деп аталады. m қабырғасы және n төбесі бар байланысты жазық график үшін, торлылық коэффициентін мына формула арқылы есептеуге болады.

Мұнда формуланың алымы берілген графиктің контурлық рангі, ал бөлімі – n төбесі бар жазық графиктің ең үлкен мүмкін контурлық рангі. Торлылық коэффициенті ағаштар үшін 0-ден, ал максималды жазық графиктер үшін 1-ге дейін өзгереді.

Құлақтың ыдырауы

Сұлбалық ранг графтың құлақтарының санын басқарады, графтың қабырғаларын жолдар мен циклдерге бөлу, көптеген граф алгоритмдерінде пайдалы. Атап айтқанда, граф 2 төбесімен байланысқан, егер және тек егер ол ашық құлақтарға жіктеле алатын болса. Бұл – субграфтар тізбегі, онда алғашқы субграф қарапайым цикл, ал қалғандары – қарапайым жолдар. Әрбір жол бұрынғы субграфтарға жататын төбелерде басталып, аяқталады, және жолдың ішкі әрбір төбесі осы жолда алғаш рет пайда болады. Кез келген екі байланысты графтағы кез келген ашық құлақтар жіктелімінде дәл құлақтар болады.

Шамамен ағаштар

Цикломатикалық саны r болатын графты r-ға жуық ағаш деп те атайды, себебі оны ағашқа немесе орманға айналдыру үшін графтан тек r қабырғаны жою қажет. 1-ге жуық ағаш – жақын ағаш болып табылады: байланысты жақын ағаш – псевдоағаш, әрбір төбесінде тамырланған (көбінесе тривиалды) ағаштары бар цикл. Бірнеше авторлар r-жақын ағаштардағы граф алгоритмдерінің параметрленген күрделілігін, r параметрі бойынша зерттеді.

Бағытталған графиктерге жалпылау

Циклдық ранг - бағытталған графтардың инварианты, графтардағы циклдардың ұялану деңгейін өлшейді. Оның схемалық рангтан гөрі күрделі анықтамасы бар (бағытталмаған графтар үшін ағаш тереңдігінің анықтамасымен тығыз байланысты) және оны есептеу қиын. Схемалық рангқа қатысты бағытталған графтар үшін тағы бір мәселе – ең аз кері байланыс доғалары жиыны, яғни барлық бағытталған циклдарды жою үшін алынып тасталатын қабырғалардың ең кішкентай жиыны. Циклдық рангты және ең аз кері байланыс доғалары жиынын есептеу NP-қиын мәселесі болып табылады. Сонымен қатар, граф қабырғаларының бағытын ескермей, жатқан бағытталмаған графтың схемалық рангын есептеу арқылы бағытталған графтардың қарапайым инвариантын есептеуге болады. Бұл принцип цикломатикалық күрделіліктің анықтамасын құрайды, ол компьютерлік кодтың күрделілігін бағалауға арналған бағдарламалық метрика.

Есептеу химиясы

Химия және химиоинформатика салаларында молекулалық графтың контурлық рангі (ең кіші сақиналардың ең кіші жиынтығындағы сақиналар саны) кейде Фрережак саны деп аталады.

Параметрленген күрделілік

Графтардағы кейбір есептеу проблемалары жалпы жағдайда NP-толық, бірақ кішкентай схемалық рангі бар графтар үшін полиномдық уақытта шешіледі. Жолды қайта конфигурациялау мәселесі – сондай мысалдың бірі.