Teorian'ny grafika amin'ny matematika
Sampana iray amin'ny matematika misaraka ny teôrian'ny grafika izay mandalina ny rafitry ny fifandraisana misy eo amin'ny zavatra. Ireo zavatra ireo dia aseho amin'ny endrika tendrony (nodes), ary ny fifandraisana misy eo amin'izy ireo dia aseho amin'ny endrika sisiny (arcs). Na dia mety ho tsotra aza izany, ny teôrian'ny grafika dia mitana anjara toerana lehibe amin'ny sehatra isan-karazany, manomboka amin'ny siansa informatika sy ny injeniera ka hatramin'ny biolojia sy toekarena, ary na dia ny siansa sosialy aza. Maro amin'ireo olana sarotra eo amin'ny fiainana andavanandro no azo amboarina amin'ny alalan'ny grafika, ka mahatonga azy ireo ho mora kokoa ny mamakafaka sy mamaha amin'ny alalan'ny foto-kevitra matematika.
Famaritana sy singa fototra amin'ny grafika
Amin'ny fomba ofisialy, ny grafika dia matetika soratana hoe G = (V, E), izay:
– Ny V (teboka) dia andiana tendrony.
– E (edge set) dia ny andian-tsisin ...
Ohatra, raha V = {A, B, C} ary E = {(A,B), (B,C)}, dia mampiseho ny grafika fa mifandray amin'ny B i A ary mifandray amin'ny C i B. Tena ilaina ity endrika fanehoana ity amin'ny famaritana ny tambajotra an-dalana, ny fifandraisana amin'ny fisakaizana amin'ny media sosialy, ny fifandraisana amin'ny solosaina amin'ny tambajotra, ary na dia ny rafitra molekiola amin'ny simia aza.
Afaka maneho zavatra isan-karazany ny "nodes", toy ny tanàna, mpampiasa, solosaina, na fototarazo. Ny "edges" kosa dia maneho fifandraisana, toy ny lalana eo amin'ny tanàna, fisakaizana, tariby tambajotra, na fifandraisana ara-biolojika.
Karazana grafika
Ny teorian'ny grafika dia mahafantatra karazana grafika maro, miankina amin'ny toetran'ny fifandraisana aseho:
1. Grafika tsy voatarika
Tsy misy lalana ny andaniny roa. Raha mifandray amin'i B i A, dia mifandray amin'i A koa i B. Ohatra: fisakaizana roa tonta.
2. Grafika voatarika (grafika voatarika / digrafa)
Manana lalana ny sisiny, izay aseho amin'ny endrika tsiroaroa voalamina (A → B). Izany dia mety amin'ny famolavolana fifandraisana "manaraka" amin'ny media sosialy na ny fizotran'ny asa.
3. Grafika misy lanja
Manana lanja ny sisiny tsirairay, toy ny halavirana, ny vidiny, na ny fotoana lany amin'ny dia. Matetika ampiasaina ny grafika lanja mba hahitana ny lalana haingana indrindra na mora indrindra.
4. Grafika tsotra
Tsy misy tadivavarana ary tsy misy sisiny roa mampitohy fatotra mitovy tsiroaroa izy io.
5. Grafika maro
Mamela ny sisiny mihoatra ny iray hampifandray ireo node roa mitovy, ilaina amin'ny famolavolana fifandraisana maromaro ao anaty rafitra iray.
6. Grafika feno (grafika feno)
Mifandray amin'ny sisiny iray ny tendrony roa. Ny grafika feno misy tendrony n dia mazàna soratana hoe Kₙ. Matetika ampiasaina hiresahana ny fetra ambony indrindra amin'ny fifandraisana izany.
7. Grafika bipartite
Azo zaraina ho vondrona roa ny andiana "nodes", ary ny sisiny kosa dia mampifandray fotsiny ireo "nodes" avy amin'ny vondrona samihafa. Ohatra: mpiasa sy asa mifanandrify, mpianatra sy fampianarana.
8. Hazo
Grafika mifandray tsy misy tsingerina. Tena ilaina amin'ny rafitry ny angon-drakitra, ny ambaratongam-pandaminana ary ny fanehoana fanapahan-kevitra ny hazo.
Hevitra manan-danja amin'ny Teorian'ny Grafika
Ireto avy ny sasany amin'ireo foto-kevitra fototra ao amin'ny teorian'ny grafika:
1. Degree Node
Ny degrean'ny node dia ny isan'ny sisiny mifamatotra amin'io node io. Ao amin'ny grafika tarihina, dia misy ny in-degree (ny isan'ny sisiny miditra) sy ny out-degree (ny isan'ny sisiny mivoaka). Ilaina ny degre amin'ny fandrefesana ny "fifandraisana" amin'ny node ao anaty tambajotra.
2. Lalana, Lalan-kely, ary Bisikileta
- Ny lalana dia andiana tendrony mifandray amin'ny sisiny.
- Ny lalana dia lalana tsy miverimberina amin'ny sisiny.
– Ny tsingerina dia lalana iray izay miverina any amin'ny node voalohany tsy misy sisiny miverimberina (ary matetika tsy misy node miverimberina afa-tsy ny fiandohana/fiafarana).
Zava-dehibe ity hevitra ity mba hahatakarana ny fitetezana ao anaty tambajotra, ny lalana mety hitranga, ary ny famantarana ny tadivavarana ao anaty rafitra.
3. Fifandraisana
Voalaza fa mifandray ny grafika iray raha toa ka manana lalana mampifandray azy ireo ny tendrony roa tsirairay. Ao amin'ny grafika voatarika, misy foto-kevitra manokana kokoa momba ny fifandraisana, toy ny mifandray mafy (ny tendrony tsirairay dia afaka mahatratra ny tendrony hafa rehetra amin'ny alàlan'ny sisiny).
Tena zava-dehibe ny fifandraisana amin'ny famakafakana tambajotra fifandraisana—ohatra, ny hoe mbola afaka mifampiresaka ve ireo solosaina rehetra ao amin'ny tambajotra raha toa ka tapaka ny fifandraisana iray.
4. Subgrafy sy Singa
Ny subgraph dia vondron-tsary miforona avy amin'ny vondron-tsary misy tendrony sy sisiny. Ny singa mifandray dia ny subgraph ambony indrindra izay mbola mifandray. Ao amin'ny fanadihadiana tambajotra sosialy, ny singa dia afaka maneho vondrona mifandray nefa misaraka.
Teôrema sy olana klasika
Efa ela no nisy ny teorian'ny grafika, nanomboka tamin'ny olana malaza momba ny Tetezan'i Königsberg izay novahan'i Leonhard Euler tamin'ny taonjato faha-18. Noporofoin'i Euler fa tsy azo atao ny miampita ireo tetezana fito indray mandeha monja ary miverina any amin'ny toerana niaingana, ka izany no nanorenana ny fototry ny teorian'ny grafika maoderina.
Ireto misy lohahevitra mahazatra sasany amin'ny teoria grafika:
1. Ny lalan'i Euler sy Hamilton
– Mandalo indray mandeha katroka amin'ny sisiny tsirairay ny lalana Eulerianina. Ny fepetra hisian'ny lalana Eulerianina ao anaty grafika tsy misy tari-dalana dia mifandraika amin'ny isan'ny tendrony amin'ny ambaratonga hafahafa.
– Mitsidika ny tendrony tsirairay indray mandeha monja ny lalan'i Hamilton. Tsy tahaka ny olan'i Euler, sarotra kokoa ny olan'i Hamilton, ary maro amin'ireo karazany no NP-hard amin'ny kajy.
2. Fandokoana sary
Ny fandokoana grafika dia ny fanomezana loko amin'ny tendrony (na sisiny) mba tsy hitovy loko ny tendrony mifanila. Ny fampiharana malaza dia ny olana momba ny fandokoana sarintany, izay mitarika amin'ny teôrema fa ny sarintany fisaka rehetra dia azo lokoina amin'ny loko efatra farafahakeliny (ny Teôrema Efatra Loko).
3. Grafika fisaka
Azo atao sary amin'ny toerana fisaka tsy misy sisiny mifanena ny grafika fisaka. Ampiasaina betsaka amin'ny famolavolana faritra elektronika sy ny fandrafetana tambajotra ny grafika fisaka.
Algorithma manan-danja amin'ny Teorian'ny Graph
Ao amin'ny siansa informatika, ny teoria grafika no fototry ny algorithm manan-danja maro:
– BFS (Breadth-Fikarohana Voalohany) sy DFS (Depth-Fikarohana Voalohany) ho an'ny fitetezana grafika, fikarohana singa, fitadiavana tsingerina, ary topolojia.
– Dijkstra mba hahitana ny lalana fohy indrindra ao anaty grafika misy lanja misy lanja tsy miiba.
– Bellman–Ford ho an'ny lalana fohy indrindra izay afaka miatrika lanja ratsy.
– Kruskal sy Prim mba hahitana ny hazo mivelatra kely indrindra, izay ilaina amin'ny famolavolana tambajotra miaraka amin'ny vidiny faran'izay kely indrindra.
Ireo algorithm ireo dia mampiseho ny fomba ilalaovan'ny foto-kevitra matematika amin'ny grafika anjara mivantana amin'ny famahana olana azo ampiharina.
Fampiharana ny Teorian'ny Grafika eo amin'ny Fiainana Tena Izy
Mahery vaika ny teoria grafika satria afaka mamolavola "fifandraisana" amin'ny toe-javatra isan-karazany:
1. Fitaterana sy fitetezam-paritra
Ny "nodes" dia maneho ny fihaonan-dalana, ny sisiny dia maneho ny lalana, ary ny lanja dia maneho ny halavirana na ny fotoana lany. Mampiasa algorithm grafika ny rafitra fitetezana mba hamaritana ny lalana tsara indrindra.
2. Tambajotra informatika sy aterineto
Ny "routers" sy ny "servers" dia miasa toy ny "nodes", ary ny tariby na ny fifandraisana kosa miasa toy ny "edges". Ny famakafakana grafika dia ampiasaina hanatsarana ny fifamoivoizana angona sy hanatsarana ny faharetan'ny tambajotra.
3. Tambajotra sosialy
Ireo mpampiasa dia toy ny node, ireo fifandraisana dia toy ny edges. Ampiasaina hamantarana ireo vondrom-piarahamonina, handrefesana ny fiantraikany (centrality), ary handinihana ny fizarana vaovao ny teoria grafika.
4. Biôlôjia sy simia
Ampiasaina hanaovana modely ny tambajotran'ny fototarazo, ny fifandraisan'ny proteinina, na ny rafitra molekiola ny grafika. Ny fikarohana bioinformatika maro dia miankina amin'ny fanadihadiana grafika amin'ny ambaratonga lehibe.
5. Fitantanana tetikasa sy indostrialy
Ampiasaina amin'ny fandrindrana asa (ohatra, PERT/CPM) ny grafika tarihina mba hahitana ny filaharan'ny asa mahomby sy ny lalan-kizorana mitsikera.
Penutup
Ny teorian'ny grafika amin'ny matematika dia ny fandalinana ny rafitry ny fifandraisana amin'ny alàlan'ny node sy ny sisiny. Miaraka amin'ny karazana grafika isan-karazany, ny foto-kevitra toy ny degre, ny lalana, ny tsingerina, ary ny algorithm fikarohana sy fanatsarana, ny teorian'ny grafika dia fitaovana tena azo ovaina sy mahery vaika. Ny tanjany dia ny fahafahany maneho olana sarotra amin'ny modely voarafitra sy azo dinihina . Tsy mahagaga raha fototra tena ilaina amin'ny fampandrosoana ny matematika misaraka , ny siansa informatika, ary ny fampiharana maoderina maro izay misy fiantraikany amin'ny fiainana andavanandro ny teorian'ny grafika.
Raha tianao, afaka manampy ohatra amin'ny olana miaraka amin'ny fifanakalozan-kevitra aho (ohatra momba ny lalan'i Euler, ny an'i Dijkstra, na ny fandokoana grafika) mba hampiharana bebe kokoa ity lahatsoratra ity.
