grafoak
iz. Pl. Multzoen teorian bikote multzoak (x, y), eta teoria konbinatorioan, puntuez (gailur esaten zaie) eta arkuez (erpin esaten zaie) osatutako egitura. Grafo hitzaren lehenengo zentzuan, z = (x, y) bikoteak, zeinaren multzoak osatzen baitu G grafoa, x eta y bi osagai ordena jakin batean egoteak ematen duen datuaren arabera osatuak dira, hau da, (x, y)Ć (y, x). x eta y osagaiak E eta F bi multzori dagozkie, eta multzo horiek zenbaitetan elkarren berdinak izaten dira. G, beraz, E x F biderkadura kartesiarraren zati bat da, eta (x, y) bikote guztien multzoa da. Oro har, grafoaren bikoteen x eta y osagaiak › harreman edo korrespondentzia batez lotuta daude (x › y idazten da); G grafoa › harremanaren grafoa da. Funtzioei dagokienez, kurba adierazgarri bat besterik ez da grafoa. G grafo bateko z = (x, y) bikoteetako x-en balioen multzoari G-ren lehenengo proiekzioa esaten zaio; G-ren definizioaren multzoa da. y-en multzoa, berriz, bigarren proiekzioa da, G-ren balioen multzo esaten zaiona. ■ Grafoen teoria Leonhard Eulerrek azaldutako konbinatoriako problema batetik sortu zen, Königsberg-en zubien problematik hain zuzen. Eulerrek puntuez, gailurrak, eta gailur horiek lotzen zituzten arkuez, erpinak, osatutako grafoak asmatu zituen. Ideia hori aurrerakuntza handia izan zen, garrantzizko eredua baitzen matematikaren hainbat aplikazioetarako: garraio eta zirkulazio sareak, zirkuitu elektrikoak, programazio algoritmoak, informazioaren trataera, jokoen teoria, etab. Hainbat grafo mota bereizten dira. Erpinetan ibilbidearen zentzua jartzen bada, grafoa zuzendua da. Bestalde, jatorri eta helburu bera duten hainbat erpin egon daiteke, eta halakoetan grafoa multigrafoa dela esaten da. Bide bat, grafo batean, gailurren eta bi gailur lotzen dituen erpinen segida da. Leonhard Eulerrek adierazi zuen problemak aditzera ematen du bide bat ezin igaro dela bitan erpin beretik: halako bideari Eulerren bidea esaten zaio. Horren soluzioa nahiko erraza da. Aldiz, gailur beretik bi aldiz igarotzen ez den bidea bilatzea (Hamiltonen bidea) oso zaila da. Merkatari bidaiatzailearen problema da hori, hiri beretik igarotzen ez den ibilbide merkea bilatzen duenarena alegia. Gaur egun ez da horren emaitza orokorrik ezagutzen. Grafo batean, zirkuitu esaten zaio bide itxi bati, irteera puntura itzultzen denari hain zuzen.
