Träd (grafteori)

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 16 juni 2020; kontroller kräver 6 redigeringar .

Ett träd  är en sammankopplad acyklisk graf . [1] Anslutning innebär närvaron av en rutt mellan valfritt par av hörn, acyklicitet betyder frånvaron av cykler. Särskilt av detta följer att antalet kanter i ett träd är en mindre än antalet hörn, och det finns en och bara en väg mellan vilket par av hörn som helst.

Skogen  är mycket träd.

Ett riktat (riktat) träd  är en acyklisk digraf ( en riktad graf som inte innehåller cykler), där endast en vertex har en nollgrad av ingång (det finns inga bågar i den), och alla andra hörn har en ingångsgrad på 1 (exakt en båge leder till dem). En vertex med nollgrad av ingång kallas trädets rot , hörn med noll grad av utfall (från vilken ingen båge kommer ut) kallas terminala hörn eller blad . [2]

Relaterade definitioner

  1. trädrotnivån är 0;
  2. nivån för någon annan nod är en högre än nivån på roten för det närmaste underträdet i trädet som innehåller den noden.

Binärt träd

Termen binärt träd (termen binärt träd används också) har flera betydelser:

N-ary trees

N-ära träd definieras i analogi med ett binärt träd. De har också riktade och oriktade fall, såväl som motsvarande abstrakta datastrukturer.

Egenskaper

Trädräkning

för antalet icke-isomorfa rotade träd med hörn uppfyller den funktionella ekvationen . för antalet icke- isomorfa träd med hörn kan representeras med hjälp av listserien för rotade träd: var och är vissa konstanter, , .

Trädkodning

Se även

Anteckningar

  1. § 13. Definition av ett träd // Föreläsningar om grafteori / Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I. - M . : Nauka, Fizmatlit, 1990. - P. 53. - 384 sid. — 22 000 exemplar.  — ISBN 5-02-013992-0 .
  2. Alfs Berztiss. Kapitel 3. Grafteori. 3.6. Träd // Datastrukturer = AT Berztiss. data struktur. teori och praktik. - M. : Statistik, 1974. - S. 131. - 10 500 ex.
  3. Diskret matematik: Algoritmer. Cayleys formel (otillgänglig länk) . Hämtad 29 oktober 2009. Arkiverad från originalet 14 juni 2009. 

Litteratur