| dbo:abstract
|
- A matroid a modern matematika egy igen újnak számító fogalma, melyet 1935-ben vezetett be amerikai matematikus; maga a szó latin-görög szóösszetétel, melynek jelentése: „mátrix-szerű”. Némileg, bár elég pontatlanul tényleg a mátrix-fogalom egy általánosításáról van szó (ha a mátrixokat mint oszlopaik vagy soraik halmazait és ezek részhalmazait tekintjük), de pontosabb és hasznosabb, ha a matroid fogalmát egy olyan, halmazokból álló, axiómarendszerrel leírt konstrukciónak tekintjük, mely a lineáris függetlenség / lineáris összefüggőség fogalmát próbálja absztrahálni. Egy U halmaz (alaphalmaz) feletti matroidon lényegében olyan nem üres (azaz U részhalmazai P(U) halmazának egy részhalmazát) érthetünk – tagjait független halmazoknak nevezzük – melyre igaz, hogy bármely két különböző számosságú független halmaz esetén a kisebb számosságú bővíthető úgy egy rajta kívüli, a nagyobb számosságúban lévő elemmel, hogy az így bővített halmaz is független. A matematikailag pontosabb leírás lentebb található. A matematikában a lineáris algebra és a gráfelmélet régóta jegyben járnak: a matroidelmélet eme kapcsolat egyik törvényesítésének vagy gyermekének tekinthető, és legfontosabb fogalmai, eredményei az e két területről származóak némileg új szemléletben való megfogalmazásai és általánosításai. A leginkább a kombinatorika alterületének számítható, bár fontos számítógéptudományi vonatkozásai is vannak. A szakemberei szerint ugyanis a matroidok meghatározhatóak olyan „leszálló” halmazrendszerekként is, melyekre egy, a halmazrendszer alaphalmazán értelmezett súlyfüggvény meghatározta, pontosan definiált értelemben mohó algoritmus tetszőleges súlyfüggvényt véve is megadja ennek optimumát (a pontos meghatározást ld. lent). A felfedezés óta elmúlt évtizedekben több könyv is megjelent e tárgykörben. A matroidelmélet sok alkalmazásra talált az áramkörök analízisében, a kapcsoláselméletben, a lineáris programozásban, a és a gráfelméletben. (hu)
- A matroid a modern matematika egy igen újnak számító fogalma, melyet 1935-ben vezetett be amerikai matematikus; maga a szó latin-görög szóösszetétel, melynek jelentése: „mátrix-szerű”. Némileg, bár elég pontatlanul tényleg a mátrix-fogalom egy általánosításáról van szó (ha a mátrixokat mint oszlopaik vagy soraik halmazait és ezek részhalmazait tekintjük), de pontosabb és hasznosabb, ha a matroid fogalmát egy olyan, halmazokból álló, axiómarendszerrel leírt konstrukciónak tekintjük, mely a lineáris függetlenség / lineáris összefüggőség fogalmát próbálja absztrahálni. Egy U halmaz (alaphalmaz) feletti matroidon lényegében olyan nem üres (azaz U részhalmazai P(U) halmazának egy részhalmazát) érthetünk – tagjait független halmazoknak nevezzük – melyre igaz, hogy bármely két különböző számosságú független halmaz esetén a kisebb számosságú bővíthető úgy egy rajta kívüli, a nagyobb számosságúban lévő elemmel, hogy az így bővített halmaz is független. A matematikailag pontosabb leírás lentebb található. A matematikában a lineáris algebra és a gráfelmélet régóta jegyben járnak: a matroidelmélet eme kapcsolat egyik törvényesítésének vagy gyermekének tekinthető, és legfontosabb fogalmai, eredményei az e két területről származóak némileg új szemléletben való megfogalmazásai és általánosításai. A leginkább a kombinatorika alterületének számítható, bár fontos számítógéptudományi vonatkozásai is vannak. A szakemberei szerint ugyanis a matroidok meghatározhatóak olyan „leszálló” halmazrendszerekként is, melyekre egy, a halmazrendszer alaphalmazán értelmezett súlyfüggvény meghatározta, pontosan definiált értelemben mohó algoritmus tetszőleges súlyfüggvényt véve is megadja ennek optimumát (a pontos meghatározást ld. lent). A felfedezés óta elmúlt évtizedekben több könyv is megjelent e tárgykörben. A matroidelmélet sok alkalmazásra talált az áramkörök analízisében, a kapcsoláselméletben, a lineáris programozásban, a és a gráfelméletben. (hu)
|
