GRA­FO

Mate - - Glossario -

Il gra­fo è una strut­tu­ra ma­te­ma­ti­ca for­ma­ta da un in­sie­me fi­ni­to di ele­men­ti det­ti ver­ti­ci, o no­di, al­cu­ni dei qua­li so­no con­si­de­ra­ti uni­ti tra lo­ro e per que­sto so­no det­ti “adia­cen­ti”. Di so­li­to si rap­pre­sen­ta­no i ver­ti­ci come pun­ti nel pia­no, e il le­ga­me di adia­cen­za si rap­pre­sen­ta con un “ar­co” che con­giun­ge i due pun­ti. Per esem­pio la re­te di stra­de di una cit­tà for­ma un gra­fo in cui gli in­cro­ci so­no i ver­ti­ci e le stra­de so­no gli ar­chi. Un al­tro ti­po di gra­fo è la re­te in­ter­net: i no­di so­no tut­ti i com­pu­ter del mon­do, e due com­pu­ter so­no adia­cen­ti se so­no con­nes­si di­ret­ta­men­te tra di lo­ro. La na­sci­ta del­la teo­ria dei gra­fi si fa ri­sa­li­re a Eu­le­ro, che nel Set­te­cen­to di­mo­strò che non era pos­si­bi­le at­tra­ver­sa­re i set­te pon­ti del­la cit­tà di Kö­nig­sberg sen­za pas­sa­re due vol­te sul­lo stes­so pon­te. Per fa­re que­sto con­si­de­rò i pun­ti di ar­ri­vo e par­ten­za dei pon­ti come ver­ti­ci di un gra­fo e i pon­ti stes­si come ar­chi. In ge­ne­ra­le un gra­fo in cui è pos­si­bi­le at­tra­ver­sa­re tut­ti gli ar­chi e tor­na­re al ver­ti­ce di par­ten­za sen­za pas­sa­re due vol­te per lo stes­so ar­co è chia­ma­to “eu­le­ria­no”, e quel­lo di Kö­nig­sberg

non lo era. I gra­fi pos-

so­no es­se­re orien­ta­ti o non orien­ta­ti. Nel ca­so non orien­ta­to, la re­la­zio­ne di adia­cen­za tra due ver­ti­ci è sim­me­tri­ca. Per esem­pio, se fac­cia­mo un gra­fo del­le per­so­ne che, du­ran­te una fe­sta, si strin­go­no la ma­no, gli ar­chi tra due ver­ti­ci non sa­ran­no orien­ta­ti, per­ché se una per­so­na strin­ge la ma­no a un’al­tra an­che que­sta, ne­ces­sa­ria­men­te, le strin­ge la ma­no. In­ve­ce in un gra­fo orien­ta­to la re­la­zio­ne tra due ver­ti­ci ha un ver­so. Per esem­pio, in una re­te stra­da­le, ogni ar­co ha un so­lo sen­so di mar­cia e le stra­de a dop­pio sen­so si rap­pre­sen­ta­no con due ar­chi di orien­ta­men­to op­po­sto. La teo­ria dei gra­fi vie­ne uti­liz­za­ta in mol­ti cam­pi per rap­pre­sen­ta­re re­la­zio­ni e pro­ces­si in fi­si­ca, bio­lo­gia, in­for­ma­ti­ca, so­cio­lo­gia e lin­gui­sti­ca. Per esem­pio, i gra­fi si usa­no in bio­lo­gia per de­scri­ve­re le re­la­zio­ni tra gli an­ti­ge­ni e gli an­ti­cor­pi, e in so­cio­lo­gia si usa­no per rap­pre­sen­ta­re le re­ti di re­la­zio­ni so­cia­li, come per esem­pio la re­te di Fa­ce­book. La pros­si­ma vol­ta che chie­de­te l’ami­ci­zia a qual­cu­no, ri­cor­da­te­vi che sta­te co­struen­do un' ar­co...lo­gia dei te­sti).

Newspapers in Italian

Newspapers from Italy

© PressReader. All rights reserved.