Střední algebra - Median algebra - Wikipedia

v matematika, a střední algebra je sada s a ternární provoz ${ displaystyle langle x, y, z rangle}$ splňující soubor axiomů, které zobecňují pojem medián nebo většinová funkce, jako Booleovská funkce.

Axiomy jsou

1. ${ displaystyle langle x, y, y rangle = y}$
2. ${ displaystyle langle x, y, z rangle = langle z, x, y rangle}$
3. ${ displaystyle langle x, y, z rangle = langle x, z, y rangle}$
4. ${ displaystyle langle langle x, w, y rangle, w, z rangle = langle x, w, langle y, w, z rangle rangle}$

Z druhé a třetí axiomy vyplývá komutativita: je možné (ale není to snadné) ukázat, že v přítomnosti ostatních tří je axiom (3) nadbytečný. Čtvrtý axiom implikuje asociativitu. Existují i ​​další možné systémy axiomů: například dva

• ${ displaystyle langle x, y, y rangle = y}$
• ${ displaystyle langle u, proti, langle u, w, x rangle rangle = langle u, x, langle w, u, v rangle rangle}$

také dostačující.

V Booleova algebra, nebo obecněji a distribuční mříž, střední funkce ${ Displaystyle langle x, y, z rangle = (x vee y) klín (y vee z) klín (z vee x)}$ uspokojuje tyto axiomy, takže každá booleovská algebra a každá distribuční mřížka tvoří střední algebru.

Birkhoff a Kiss ukázali, že střední algebra s prvky ${ displaystyle 0}$ a ${ displaystyle 1}$ uspokojující ${ displaystyle langle 0, x, 1 rangle = x}$ je distribuční mříž.

Vztah ke středním grafům

A střední graf je neorientovaný graf ve kterém pro každé tři vrcholy ${ displaystyle x}$, ${ displaystyle y}$, a ${ displaystyle z}$ existuje jedinečný vrchol ${ displaystyle langle x, y, z rangle}$ kterému patří nejkratší cesty mezi libovolnými dvěma z ${ displaystyle x}$, ${ displaystyle y}$, a ${ displaystyle z}$. Pokud je to váš případ, pak operace ${ displaystyle langle x, y, z rangle}$ definuje střední algebru s vrcholy grafu jako jeho prvky.

Naopak v jakékoli střední algebře lze definovat interval ${ displaystyle [x, z]}$ být souborem prvků ${ displaystyle y}$ takhle ${ displaystyle langle x, y, z rangle = y}$. Jeden může definovat graf ze střední algebry vytvořením vrcholu pro každý prvek algebry a hrany pro každý pár ${ displaystyle (x, z)}$ takový, že interval ${ displaystyle [x, z]}$ neobsahuje žádné další prvky. Pokud má algebra vlastnost, že každý interval je konečný, pak je tento graf středním grafem a přesně představuje algebru v tom, že střední operace definovaná nejkratšími cestami v grafu se shoduje s původní střední operací algebry.

Reference

• Birkhoff, Garrett; Kiss, S.A. (1947). „Ternární operace v distribučních mřížkách“. Býk. Amer. Matematika. Soc. 53 (8): 749–752. doi:10.1090 / S0002-9904-1947-08864-9.
• Isbell, John R. (Srpen 1980). "Mediánová algebra". Trans. Amer. Matematika. Soc. Americká matematická společnost. 260 (2): 319–362. doi:10.2307/1998007. JSTOR  1998007.
• Knuth, Donald E. (2008). Úvod do kombinatorických algoritmů a booleovských funkcí. Umění počítačového programování. 4.0. Upper Saddle River, NJ: Addison-Wesley. str. 64–74. ISBN  0-321-53496-4.

externí odkazy

• Důkaz o střední algebře