Nulita (teorie grafů) - Nullity (graph theory)

The neplatnost a graf v matematický Předmět teorie grafů může znamenat jedno ze dvou nesouvisejících čísel. Pokud má graf n vrcholy a m hrany, pak:

  • V teorie matic z grafů je neplatnost grafu neplatnost matice sousedství A grafu. Nulita A darováno n − r kde, r je hodnost matice sousedství. Tato nullita se rovná multiplicitě vlastní číslo 0 ve spektru matice sousedství. Viz Cvetkovič a Gutman (1972), Cheng a Liu (2007) a Gutman a Borovićanin (2011).
  • V teorie matroidů neplatnost grafu je neplatnost orientovaného matice výskytu M spojené s grafem. Nulita M darováno m − n + Ckde C je počet komponent grafu a n − C je hodnost orientované matice dopadu. Tento název se používá jen zřídka; číslo je běžněji známé jako hodnost cyklu, cyklomatické číslonebo hodnost obvodu grafu. Rovná se hodnosti spolupracovníkagrafický matroid grafu. Rovná se to také neplatnosti Laplaciánská matice grafu, definovaný jako L = D - A, kde D je úhlopříčná matice vrcholných stupňů; Laplaciánská nulita se rovná hodnosti cyklu, protože L = M MT (M krát vlastní transpozice).

Viz také

Rank (teorie grafů)

Reference

  • Bo Cheng a Bolian Liu (2007), O neplatnosti grafů. Elektronický deník lineární algebry, sv. 16, článek 5, s. 60–67.
  • Dragoš M. Cvetkovič a Ivan M. Gutman (1972), Algebraická multiplicita čísla nula ve spektru bipartitního grafu. Matematički Vesnik (Bělehrad), sv. 9, s. 141–150.
  • Ivan Gutman a Bojana Borovićanin (2011), Neplatnost grafů: aktualizovaný průzkum. Zbornik Radova (Bělehrad), sv. 14, č. 22 (Vybraná témata k aplikacím Graph Spectra), s. 137–154.