A grafikonok segítségével megoldhatja a problémákat
Grafikus elmélet - a 18. század végén jelent meg, és most egy nagyon erős és folyamatosan fejlődő matematikai eszközré vált.
Sok esetben az élet, a régi szokás, hogy arra kényszerítenek minket, hogy papírra vonzzák az embereket, telepeket, vegyszereket stb. Ábrázoló pontokat, és ezeket a pontokat vonalakkal vagy nyilakkal kapcsolják, ami bizonyos kapcsolatokat jelent. Az ilyen rendszerek mindenütt különböző neveken fordulnak elő: szociogramok (pszichológiában), szimplexek (topológiában), elektromos áramkörök (a fizikában), szervezeti ábrák (közgazdaságtanban), kommunikációs hálózatok, genealógiai fák stb. D. Koenig, kétségtelenül az első, azt javasolta, hogy az ilyen rendszereket "gráfok" -nak hívják és rendszeresen tanulmányozzák tulajdonságaikat.
A gráfelméleti alapfogalmak közül az egyik a csúcs fogalma. A grafikonelméletben feltételezik, hogy az elsődleges és nem definiált. Nem nehéz elképzelni saját intuitív szinten. Általában a gráf csúcsai világosan ábrázoltak körökként, téglalapokként más ábrákon (1. Minden gráfban legalább egy csúcsnak jelen kell lennie.
A grafikonelmélet másik alapkoncepciója az ív. Általában az ívek egyenes vonalak vagy görbék összekötő szegmensei. Az ív két végének egybe kell esnie egy csúcsponttal. Abban az esetben, ha az ív két vége egybeesik ugyanazon csúcsponttal, nem zárható ki. Például a 2. ábrán - az ívek megengedett képét és a 3. ábrát - elfogadhatatlan:
A grafikonelméletben kétféle ív használható: nem irányított vagy irányított (orientált). A csak orientált íveket tartalmazó gráfot orientált gráfnak vagy digraphnak nevezik.
Az ívek lehetnek egyirányúak, mindegyik ívnek csak egy iránya van, vagy kétirányú.
A legtöbb alkalmazásban lehetséges, hogy jelentésvesztés nélkül cserélje ki a nem irányított ívet kétirányú ívvel és kétirányú ívvel két egyirányú ívvel. Például, amint azt az 1. ábra mutatja. 4.
Általánosságban egy gráfot vagy közvetlenül úgy alakítunk ki, hogy minden ívnek ugyanaz az iránykarakterisztikája legyen (például mindegyik egyirányú), vagy transzformációval hozható létre erre a formára. Ha az AB ív irányul, akkor azt jelenti, hogy a két vége közül az egyik (A) a kezdet, és a második (B) a vég. Ebben az esetben azt mondják, hogy az AB ív kezdete az A csúcs, és a vég a B csúcs, ha az ív A-b irányban van irányítva, vagy - az AB ív az A csúcsból származik, és belép B-be (5. ábra).
A grafikon két csúcsa, amelyet egy ív csatlakoztat (néha az ív tájolásától függetlenül) szomszédos csúcsoknak nevezzük.
A grafikonok tanulmányozásában fontos fogalom az út fogalma. Pálya A1, A2. An definíciója az A1, A2 csúcsok véges sorrendjének (tuple). A és ívek A1, 2, A2, 3. An-1, n egymás után összekapcsolja ezeket a csúcsokat.
A grafikonelmélet egyik fontos fogalma a kapcsolódás fogalma. Ha a gráf bármelyik két csúcsához létezik legalább egy összekötési útvonal - a grafikonról azt mondják, hogy csatlakozik.
Például, ha egy emberi vérkeringést ábrázol egy grafikon formájában, ahol a csúcsok megfelelnek a belső szerveknek, és a vér kapillárisok ívének, akkor egy ilyen grafikon nyilvánvalóan összefügg. Meg lehet-e mondani, hogy a két önkényes ember keringési rendszere összefüggéstelen grafikon? Nyilvánvaló, hogy nem, mert a természetben vannak úgynevezett. "Sziámi ikrek".
A kapcsolat nemcsak a grafikon minőségi jellemzője (összekapcsolt / nem kapcsolódó), hanem mennyiségi is lehet.
A grafikon K-kapcsoltnak mondható, ha minden csúcsa más csúcsok K-jához kapcsolódik. Néha gyengén és erősen összefüggő grafikonokról beszélnek. Ezek a fogalmak szubjektívek. A kutató a gráfot erősen összekapcsolja, ha a csúcsok mindegyikében a szomszédos csúcsok száma a kutató szerint nagy. Néha a kapcsolat jellegét nem egy, hanem egy (tetszőleges) csúcs jellegzetessége határozza meg. Ezután a típus definíciói: a grafikon K-kapcsoltnak mondható, ha legalább egyik csúcsa más csúcsok K-jával kapcsolódik.
Például egy gyermek figurája egy személynek (6. ábra) egy grafikon, amelynek maximális kapcsolata 4.
A grafikon egy másik jellemzőjét, amelyet számos problémában tanulmányoznak, gyakran egy gráf erejének nevezik. Ez a jellemző a két csúcsot összekötő ívek számának felel meg. Ebben az esetben az ellenirányú íveket gyakran külön-külön kell figyelembe venni.
Például ha egy gráf csúcsai a feldolgozási információk csomópontjai, és az ívek egymás közötti információátvitel egyirányú csatornái, akkor a rendszer megbízhatóságát nem a csatornák teljes száma határozza meg, hanem a legkisebb számú csatorna bármely irányban.
A teljesítmény, például a kapcsolódás, definiálható mind a grafikon csúcsainak mindegyik párján, és néhány (tetszőleges) pár esetében.
A grafikon alapvető jellemzője annak dimenziója. Ezt a kifejezést általában a gráfban levő csúcsok és ívek száma jelenti. Néha ez az érték a két típus elemeinek összege, néha termékként, néha csak egy (egy vagy másik) elem elemeinek számával.
A grafikonokkal modellezett objektumok nagyon eltérőek. A specifitás tükrözése iránti vágy nagyszámú grafikonfajták leírásához vezetett. Ez a folyamat jelenleg is folytatódik. Számos kutató saját célokra új fajtákat vezet be, és többé-kevésbé sikeres matematikai kutatást végez.
A sokszínűség középpontjában néhány meglehetősen egyszerű ötlet van, amelyekről itt beszélünk.
A grafikonok színezése nagyon kedvelt módja a grafikonok módosításának.
Ez a technika lehetővé teszi a modell láthatóságának növelését és a matematikai terhelés növelését. A színezés módjai eltérőek lehetnek. Egy vagy másik szabály szerint mindkét ív és csúcs színes. A festés egyszer meghatározható, vagy idővel megváltoztatható (azaz ha a grafikon megszerzi a tulajdonságait); a színek bizonyos szabályokkal átalakíthatók stb.
Például hagyd, hogy a grafikon az emberi vérkeringés modellje, ahol a csúcsok megfelelnek a belső szerveknek és az ívek a vérkeringésbe. Vérrel és vénákkal festjük az artériákat - kék. Ezután a következő kijelentés nyilvánvaló: a vizsgált grafikonon (8. ábra) csak két csúcs van, amelyek kimenő piros ívek (az ábrán a vörös szín merészen látható).
Néha az objektum elemei, a csúcsok által modellezett, lényegesen eltérő jellegűek. Vagy hasznos lehet néhány fiktív elem hozzáadása az objektum tényleges elemeihez a formalizálás folyamán. Ebben és néhány más esetben a gráf csúcsai természetesen osztályokra (részekre) oszthatók. Két típusú csúcsokat tartalmazó grafikon bipartitnak nevezhető, és így tovább. Ebben az esetben a grafikonkorlátozások száma olyan szabályokat vezet be, amelyek különböző típusú csúcsok kapcsolatára vonatkoznak. Például: "Nincs olyan ív, amely összekapcsolná az azonos típusú csúcsokat." Az ilyen típusú grafikonok egyikét a "Petri net" (9. ábra) nevezik, és meglehetősen elterjedt. A Petri hálókat részletesen tárgyaljuk a sorozat következő cikkében.
A finomság fogalma nemcsak a csúcsokra, hanem az ívekre is alkalmazható.
A grafikonok segítségével megoldhatja a problémákat.