Co znamená slovo simplex?

Hvězdná obloha nám připomíná, že body jsou základní abstrakcí, základem okolního prostoru.

úvod

Toto je první článek ze série věnované popisu vlastností vesmírných základen založených na prvcích (spíše než na vektorech). Báze definuje souřadnicový systém – popis prostorových prvků ve formě množiny čísel charakterizujících polohu prvku vůči základně.

Pokud je prostor metrický, pak základ určuje metrické tenzory, které umožňují určit vzdálenosti mezi prvky prostoru jejich souřadnicemi.

Základní metriku lze specifikovat buď prostřednictvím hodnot skalárních součinů, nebo prostřednictvím hodnot spojení mezi prvky základny. Základ lze tedy definovat jak v běžném geometrickém prostoru, tak v duálním prostoru – grafovém prostoru. V geometrickém prostoru budou prvky základny vrcholy simplexu. V grafu – uzly grafu.

Plán a obsah seriálu

V prvním článku si předvedeme reciprocitu simplexu a grafu. Definujme vzájemné metrické tenzory – Gramian a Laplacián základu. Propojme je s parametry grafů a simplexů. Pojďme si ukázat roli vesmírné normály.

Ve druhém definujeme souřadnicový systém založený na bodové bázi. Objekt charakterizují dva typy vzájemných souřadnic – bi- a di-souřadnice. V plném rozsahu vám souřadnice umožňují určit vzdálenosti mezi prvky mimo základní prostor.

Ve třetím článku zkoumáme užitečný koncept – skalární součin uspořádaných párů, který je zobecněním vektorové normy – druhé mocniny vzdálenosti mezi prvky prostoru.

Dále přejdeme do prostoru grafu. Řešíme Dirichletův problém. Ukazujeme, jak koncept fundamentální matice souvisí s určením vzdáleností mezi prvky mimo prostor podgrafu.

V 5. části se budeme zabývat transformací souřadnic při změně základny. Transformace bodových základen se využívají např. v úlohách lokalizace senzorů (určení jejich souřadnic).

Nakonec na závěr zvažte základ nejjednodušší struktury – hvězdný graf. Používáme jej k popisu prostoru kladných celých čísel, které lze rozložit na součin prvočísel.

Matice vzdálenosti

Mějme sadu skládající se z n prvky. Prvky mohou být geometrický bod v prostoru, uzel grafu, písmeno, slovo, dokument, osoba atd. – téměř jakýkoli předmět. Předpokládejme, že je známo stupeň blízkosti nastavit prvky. U bodů v prostoru je stupeň blízkosti čtverec vzdálenosti mezi nimi. Ve fyzice se míra blízkosti mezi dvěma událostmi nazývá interval.

Někdy se místo druhé mocniny vzdálenosti používá termín “kvadrance”, ale protože jej používáme zřídka, budeme často používat eufoničtější termín “vzdálenost”. Druhou mocninu vzdálenosti mezi prvky budeme označovat jako: . Pokud mluvíme o vzdálenostech mezi prvky množiny, pak se skalár změní na matici: , malé indexy označují množinu. Nice vzdáleností od daného prvku množiny ke zbytku se skládá z množiny skalárních vzdáleností:

Definuje množinu nezávislých bodů se známými vzdálenostmi mezi nimi simplexní. Ve dvourozměrném prostoru je simplex definován 3 vrcholy (trojúhelník), v trojrozměrném prostoru – 4 (čtyřstěn) atd. – rozměr simplexu je o 1 menší než počet jeho vrcholů. Vrcholy jsou nezávislé, pokud je objem simplexu nenulový.

Vzdálenosti mezi vrcholy simplexu jsou dány vztahem matice vzdálenosti . Obrázek ukazuje pravoúhlý trojúhelník (2-rozměrný simplex) s rameny 3, 4 a přeponou 5. Jeho matice vzdálenosti má tvar:

U elektrického odporového obvodu je vzdálenost rovna efektivnímu odporu mezi uzly sítě. A protože každá elektrická síť je graf, matice vzdálenosti v teorii grafů se nazývá matice odporové vzdálenosti. Takže koncept vzdálenost univerzální – lze použít jak pro obvyklý geometrický prostor, tak pro prostor grafů. To také znamená, že každému nedegenerovanému simplexu odpovídá určitý graf a naopak.

Hraniční matice

Ve vrcholech simplexu (nebo grafu) lze definovat základ prostoru. Ale k úkolu metriky musíme definovat metrický tenzor. Matice vzdálenosti není vhodná pro roli metrického tenzoru, už jen proto, že její determinant nesouvisí s objemem simplexu (v příkladu s plochou trojúhelníku).

Již v 19. století však A. Cayley objevil, že pokud matici vzdálenosti uzavřete n-ticí jedniček, pak bude determinant výsledné matice úměrný druhé mocnině objemu simplexu. Zavolá se matice vzdálenosti ohraničená jednotkami Cayley-Mengerova matice.

Definujme operaci ohraničení symetrických matic s n-ticí a skalárem:

Pokud je matice okrajem matice, pak je to podmatice a nazývá se major (rohový) moll .

O používání indexů

Horní a/nebo spodní poloha indexů vedle tenzoru určuje typ tenzoru. Pokud se tenzory 1. řady liší pouze polohou indexů ( a např. ), pak tvoří reciproční pár.

Podle pravidel pro součin tenzorů jsou skalárním součinem (konvoluce, výsledkem je skalár) dva stejné indexy v různých výškách (), bodový součin (výsledkem je n-tice) jsou stejné indexy ve stejné výšce. ( nebo ), vnější součin (výsledkem je matice, dyáda) — dva různé indexy ( nebo ).

Velké písmeno v indexu dimenze znamená, že v této dimenzi mluvíme o pevné hodnotě – prvku ( – hodnota tuple prvku).

Tam, kde je povaha předmětu z kontextu zřejmá, indexy v zápisu vynecháme.

Metrický tenzor vzdálenosti (DMT) – Gramův základ

Matematici (JCGower) si také všimli, že je pohodlnější pracovat nikoli se vzdálenostmi samotnými mezi prvky, ale se zápornými polovičními vzdálenostmi.
To se vysvětluje skutečností, že záporné poloviční vzdálenosti odrážejí skalární součin prvků, jak vyplývá ze zveřejnění vzorce pro druhou mocninu vzdálenosti (vzdálenosti) mezi prvky:

Odtud dostáváme spojení mezi maticí vzdálenosti a maticí skalárních součinů:

Zde jsou normy prvků, úhlopříčka matice skalárních součinů. Ve formě tenzoru:

Inverzní vzorec je neméně důležitý – umožňuje vám získat matici vzdálenosti založenou na gramiánech:

Přidejme k mnoha obyčejným prvkům prostoru jeden neobvyklý. Totiž vektor normály prostoru . Normální prostor je ortogonální doplněk do prostoru prvků. Skalární součin normály s prvky běžného prostoru je roven jedné a sám se sebou je nulový.

Normála je ortogonální ke všem vektorům v prostoru, proto se také nazývá anulátor. Bude volána sada prvků obsahujících prostorovou normálu hlavní (kompletní), abychom ji odlišili od množiny, ve které není normál. Normál dáme do sady jako první.

Nyní jsme připraveni definovat metrický tenzor. Metrický tenzor vzdálenosti je sada bodových produktů mezi prvky hlavní sady:

Matice skalárních součinů (vektorů) se nazývají Gramovy matice. Pro skalární součiny prvků budeme používat stejný termín, ve zkrácené podobě – ​​Gramian. Metrický tenzor vzdálenosti je tedy gramianem hlavního základu.

Pro náš simplex tří vrcholů (pravoúhlý trojúhelník) bude mít tenzor vzdálenosti tvar:

Všimněte si, že rozměr tenzoru vzdálenosti je o dva větší než rozměr běžného vektorového tenzoru při popisu prostoru stejného rozměru. To znamená, že tento tenzor obsahuje více informací.

Pro gramians použijeme dolní indexy:

Geometrické vlastnosti DMT

Determinant metrického tenzoru souvisí s objemem simplexu. Přesný vzorec:

kde je dimenze prostoru definovaná simplexem vrcholů.

Vypočítejme plochu našeho trojúhelníku. máme. Odkud tedy. Tuto plochu lze samozřejmě získat jednoduše vynásobením délek nohou.

Další užitečnou charakteristikou obsaženou v DMT je hodnota normy ortogonálního středu báze. Z hlediska geometrie je tato norma rovna druhé mocnině poloměru opsané koule kolem vrcholů simplexu. To znamená, že ortogonální střed lze interpretovat jako -rozměrnou kouli. Ortogonální střed určuje důležité charakteristiky základny, budeme jej označovat jako . Ortocentrum je prvek prostoru s normou. Tuto normu lze nalézt jako poměr determinantů úhlových moll a dur gramiánů základu:

V našem trojúhelníku bude norma základu rovna: .

Laplaceův metrický tenzor (LMT) – Laplaciův základ

U metrického tenzoru vždy existuje inverze, která se také nazývá reciproká. Inverzi vzdálenosti říkáme metrický tenzor laplacký metrický tenzor – LMT. Připojení tenzoru:

, kde je matice identity.

Proč se stal inverzní metrický tenzor vzdálenosti laplacký? Protože jeho hlavní úhlová moll (submatice) je laplacián. Stejná matice, která popisuje uzly a spojení v grafu, se také nazývá Kirchhoffova matice. Dá se říci, že vzorec (1.8) spojuje vlastnosti simplexů a grafů. Každý Laplacián má odpovídající Gramian a naopak. Tato reciprocita umožňuje porovnávat geometrické charakteristiky simplexů s parametry grafů.

Laplaceův metrický tenzor je označen horními indexy: .

Struktura LMT

Laplaceův metrický tenzor je hlavní laplacián, okraj obyčejného (malého) laplacianu. Hranice odráží parametry základního ortocentra (1.7):

Skalár je normou ortocentra (v grafech – inverzní geometrická souvislost), – barycentrické souřadnice ortocentra. Barycentrické souřadnice jsou hmotnost souřadnice prvku vzhledem k bázi (benchmarky) – vrcholy simplexu nebo grafu. Součet vah je roven jedné – podmínka pro normalizaci barycentrických složek.

Barycentrické souřadnice ortocentra libovolného pravoúhlého trojúhelníku jsou vždy stejné

To znamená, že střed O je vyvážena stejnou hmotností prvků B и C.

Obecně řečeno, pro jakýkoli graf, který je řetězcem sekvenčně spojených článků, se souřadnice ortocentra budou lišit od nuly pouze v krajních uzlech a budou rovny 1/2.

Drobné identity

Rozšíření násobení metrických tenzorů (1.8) podle pravidel pro součin blokových matic,

získáváme 4 hlavní identity.
Součet složek barycentrických souřadnic ortocentra je roven 1:

Součet hodnot řádků (a sloupců) Laplaciána je 0. To znamená, že řádky Laplacianu představují barycentrické souřadnice určitých vektorů:

Vlastnost ekvidistance základních vrcholů (simplexu nebo grafu) od ortocentra:

Konečně, spojení mezi moll gramian a Laplacian:

Matice tvaru , kde je určitý barycentrický vektor, se nazývají matice vysílání. Lze je použít například k přesunutí počátku určité množiny dat do bodu definovaného barycentrickými souřadnicemi. Maticová data jsou projektory.

Konstrukce distanční matice pomocí Laplaciánu

Pokud máme co do činění s grafem, pak lze pomocí následujícího algoritmu sestrojit matici vzdáleností založenou na matici sousednosti. Pro matici sousednosti sestrojíme Laplacián:

Zde je transformace n-tice na diagonální matici.
Laplaciánův determinant je nula, takže jej nelze jednoduše převrátit. Je nutné z něj buď odstranit nějaký uzel, nebo jej doplnit (okrajovat) nějakým vektorem.
Laplacián ohraničíme vektorem jedniček a invertujeme výslednou matici. Hlavní vedlejší (submatice) výsledku inverze bude Greenova matice.

— počet vrcholů základny.
Greenova matice je Gramian – matice skalárních součinů vektorů směřujících ze souřadnicového středu (zde je to těžiště základny) k prvkům. K získání matice vzdáleností z Gramianu je třeba použít vzorec (1.3.1).
Nechť , kde je střed. Potom má vzorec (1.3.1) následující tvar:

Laplaciánská geometrie

Porovnejme geometrické parametry simplexu s charakteristikami laplaciána.

Simplexní objem a Laplaciánský potenciál

Věta o maticovém stromě dává do souvislosti počet kostry grafu s determinantem malého Laplaciana. V předchozích článcích byla tato hodnota nazývána skalární potenciál Laplacian:

Zde je naznačeno skrz pseudodeterminant, to jest determinant moll laplacianu (protože laplacián sám je maticí singuláru). — rozměr prostoru, o jeden menší než počet prvků základny.

Vidíme, že čím menší je počet kostry grafu (čím je jeho struktura jednodušší), tím větší je objem odpovídajícího simplexu.

Prvky laplacianu

Laplacián lze považovat jak za charakteristiku simplexu, tak za parametry vazeb mezi uzly grafu. Pokud jde o grafy, hodnoty Laplacianu jsou velikostí spojení mezi uzly (s opačným znaménkem) a na diagonále je celkový součet spojení uzlů.

Typ Laplaciána pro náš příklad:

Zde vodivost (hmotnost spojení) mezi uzly A и B rovna 16/144, mezi uzly A и C 9/144 a mezi uzly B и C není vůbec žádné spojení.

Nyní zjistíme geometrický význam prvků Laplacianu. Každý vrchol simplexu může být spojen s odpovídající protilehlou plochou. Opakem rozumíme plochu simplexu, která se daného uzlu nedotýká. Je zřejmé, že v obecném případě je taková tvář vícerozměrná. V našem trojúhelníku je to strana (úsek) naproti vrcholu. V čtyřstěnu je trojúhelník. Poklesem kolmice z daného vrcholu na protější plochu získáme výška vrcholy simplexu. Součin výšky vrcholu a plochy protilehlé plochy udává objem simplexu vynásobený rozměrem jeho prostoru:

Prvky Laplaciánu simplexu lze vyjádřit pomocí výšek vrcholů. Diagonální prvky Laplacianu jsou nepřímo úměrné výškám:

Výška vrcholu je vzdálenost k podprostoru zbývajících vrcholů báze. Tedy co
Čím větší je výška vrcholů simplexu, tím je simplex méně kompaktní. Z hlediska grafu platí, že čím větší vodivost (konektivita) vrcholů, tím kompaktnější je graf.

Nediagonální prvky jsou úměrné kosinusu úhlu mezi plochami simplexu:

Pravý úhel mezi plochami simplexu je ekvivalentní absenci spojení mezi odpovídajícími uzly v grafu.

Ze vztahů (1.12), (1.13) a (1.14.1) lze získat geometrický význam poměru stopy Laplaciana k jeho skalárnímu potenciálu. Tato hodnota souvisí se součtem čtverců ploch ploch simplexu:

Zde je rozměr okraje.

Konektivita ortocentra a grafu

Převrácená hodnota normy ortocentra základny je z geometrického hlediska rovna zakřivení. A v prostoru grafu tato norma charakterizuje jeho konektivitu. Nazvěme toto spojení geometrický a označ to jako:

Dimenze geometrické konektivity se shoduje s dimenzí velikosti spojení mezi uzly. Pokud se tedy u elektrických sítí vodivost mezi uzly měří v siemens, pak geometrická konektivita bude v siemens.

Hodnoty geometrické konektivity v různých topologiích grafů

Pro úplný graf (všechny uzly jsou připojeny ke všem uzlům) se stejnou silou spojení má výraz pro konektivitu v závislosti na počtu uzlů následující tvar:

Ve velkých grafech se hodnota konektivity shoduje s počtem připojení uzlů, jak se od takového invariantu očekává.

Vzorec (1.16.1) vyjadřuje maximální hodnotu konektivity pro daný počet uzlů. Minimální konektivita je pro stromy — grafy bez cyklů s jednou připojenou komponentou. Mezi stromy patří například otevřený řetěz a hvězda. Výraz pro minimální konektivitu je:

Pro srovnání uvádíme také konektivitu uzavřeného okruhu – střední hodnotu mezi maximální a minimální konektivitou:

V obou případech konektivita klesá lineárně s rostoucí velikostí grafu.

Pokud norma ortocentra báze charakterizuje konektivitu grafu, pak jeho barycentrické souřadnice lze interpretovat jako příspěvky ke konektivitě – hodnoty komponent ukazují, jak je uzel připojen ke grafu. Čím méně je propojena se zbytkem grafu, tím větší je hodnota této složky ortocentra. Kloubové uzly mají zpravidla záporné hodnoty komponentů konektivity. Proto je vhodné nazývat barycentrické souřadnice ortocentra vektorem konektivity.

Příklad hodnot parametrů pro graf

Pojďme si spočítat parametry oblíbeného grafu na Wikipedii.

Tento graf je ekvivalentní 6-vertexovému simplexu v 5-rozměrném prostoru. Kruhy s čísly jsou očíslované uzly grafu. Síla spojení mezi uzly (váha hran) se bere jako jedna.

Geometrická konektivita tohoto grafu je 1.663, což je průměrná konektivita na uzel. Můžete to porovnat s maximální (7.2) a minimální (0.8) konektivitou pro graf 6 uzlů. Index symetrie – 0.773.

Vektor konektivity uzlu (souřadnice barycentrického ortocentra): [0.364, 0.045, 0.273, -0.227, 0.045, 0.500]. Vidíme, že čím více spojení má uzel, tím nižší je jeho hodnota konektivity a naopak. Všimněte si záporné hodnoty konektivity 4. uzlu. Toto je jediný uzel v grafu, po odstranění se graf rozdělí na dvě nespojené složky. Je možné, že komponenty se zápornou konektivitou jsou klíčovými uzly grafu.
___
Pojďme si to shrnout. Jsou definovány reciproké metrické tenzory na prvcích prostoru, Gramian a Laplacián durové báze. Je ukázáno spojení mezi simplexy a grafy. V příštím článku si ukážeme, jak nastavit souřadnice prvků v základu.

• Matice vzdálenosti
• laplacký
• metrický tenzor
• počítat
• simplexní