Графиктің минималды дәрежесі - Minimum rank of a graph - Wikipedia

Математикада минималды дәреже Бұл график параметр үшін график G. Оған түрткі болды Колин де Вердиер графигі өзгермейді.

Анықтама

The матрица туралы бағытталмаған граф Бұл симметриялық матрица оның жолдары мен бағандары екеуі де графиктің шыңдарына сәйкес келеді. Оның элементтері барлығы 0 немесе 1, ал жолдағы элемент мен және баған j шың болған сайын нөлге тең емес мен шыңына іргелес j графикте. Жалпы, а жалпыланған көршілестік матрица - бұл диагональдан тыс нөлдердің бірдей сызбасы бар нақты сандардың кез-келген симметриялық матрицасы (диагональ элементтері кез-келген нақты сандар болуы мүмкін). Минималды дәрежесі ең кішісі ретінде анықталады дәреже графиктің кез-келген жалпыланған көршілестік матрицасының; ол арқылы белгіленеді .

Қасиеттері

Міне бірнеше қарапайым қасиеттер.

Белгілі графтар отбасыларының сипаттамасы

Графтардың бірнеше отбасыларына минималды дәрежелері бойынша сипаттама берілуі мүмкін.

  • Үшін , толық граф Қn қосулы n шыңдардың минималды дәрежесі бар. Байланыстырылған және ең төменгі деңгейге ие жалғыз графиктер - бұл толық графиктер.[4]
  • A жол сызбасы Pn қосулы n шыңдар минималды дәрежеге ие n - жалғыз n- минималды дәрежесі бар вертикальды графиктер n - 1 - бұл графикалық графиктер.[5]
  • A цикл графигі Cn қосулы n шыңдар минималды дәрежеге ие n − 2.[6]
  • Келіңіздер болуы а 2-қосылған график. Содан кейін егер және егер болса сызықты 2 ағаш.[7]
  • График бар егер және егер ғана формада болады сәйкес теріс емес бүтін сандар үшін бірге барлығына .[8]

Ескертулер

  1. ^ Фаллат – Хогбен, Бақылау 1.2.
  2. ^ Фаллат – Хогбен, Бақылау 1.6.
  3. ^ Фаллат – Хогбен, Бақылау 1.6.
  4. ^ Фаллат – Хогбен, Бақылау 1.2.
  5. ^ Фаллат-Хогбен, Қорытынды 1.5.
  6. ^ Фаллат – Хогбен, Бақылау 1.6.
  7. ^ Фаллат-Хогбен, Теорема 2.10.
  8. ^ Фаллат-Хогбен, Теорема 2.9.

Әдебиеттер тізімі

  • Фаллат, Шон; Хогбен, Лесли, «Графикпен сипатталған симметриялық матрицалардың минималды дәрежесі: сауалнама», Сызықтық алгебра және оның қолданылуы 426 (2007) (PDF), 558-582 бет.