Užití grafů v lingvistice

Ladislav Nebeský

[Rozhledy]

(pdf)

Использование графов в лингвистике / L’emploi des graphes en linguistique

Teorie grafů je odvětvím moderní matematiky. Vzbuzuje zájem i u specialistů jiných oborů jak širokými možnostmi aplikací, tak tím, že velmi závažné otázky lze v ní často formulovat s překvapivou názorností. Její počátky sahají k Eulerovi, ale samostatnou teorií se stala až v 30. letech našeho století, především zásluhou knihy D. Königa.[1] Značného rozmachu dosáhla v uplynulých 15 letech, kdy také vyšlo několik významných monografií, které jsou jí věnovány;[2] česky vyšla knížka J. Sedláčka[3] a z větší části je teorii grafů a jejím aplikacím věnována kniha K. Čulíka, V. Doležala a M. Fiedlera.[4]

Grafy se dělí především na orientované a neorientované, popř. se připouštějí i grafy smíšené. Orientovaný graf tvoří množina prvků zvaných uzly spolu s nějakou množinou uspořádaných dvojic uzlů zvaných orientované hrany. Neorientovaný graf tvoří množina uzlů spolu s nějakou množinou neuspořádaných dvojic různých uzlů zvaných (neorientované) hrany.[5] Tematicky se teorie orientovaných grafů kryje s teorií binárních relací a teorie neorientovaných grafů odpovídá teorii ireflexívních symetrických relací. Od teorie binárních relací se však teorie grafů liší povahou otázek, které si klade, i metod, kterých používá. Protože si často klade otázky kombinatorického rázu, je zpravidla považována za součást kombinatoriky. Grafy se často reprezentují abstraktní kresbou, v níž uzly jsou znázorněny jako body a hrany jako čáry, které je spojují; důležité místo zaujímají v teorii grafů rovinné grafy, tj. grafy takové, které lze znázornit v rovině tak, aby se žádné dvě čáry, které reprezentují hrany, nekřížily v bodě, který nereprezentuje uzel.[6] Protože teorie grafů nezřídka řeší úlohy geometrické podoby a topologické podstaty, je někdy řazena i do topologie.

Lze říci, že teorie grafů leží v průsečíku různých matematických teorií. Odtud také vyplývá šířka jejích aplikačních možností. S tím souvisí i to, že některé aplikace matematiky lze považovat za aplikace teorie grafů, i když je v nich užito terminologie z jiných oborů.

K vědám, v nichž lze úspěšně aplikovat teorii grafů, patří také lingvistika. Na možnosti využití grafů v lingvistice upozornil např. N. Goodman.[7] Cílevědomý postoj k této otázce zaujal S. Marcus.[8] To, jak lze využívat pojmů teorie grafů při formulování lingvistických úloh, na množství příkladů ve své knížce přesvědčivě ukazuje E. Zierer.[9] Můžeme ovšem nalézt doklady neformálního užití grafů i v ryze jazykovědné literatuře. Výrazný příklad toho najdeme v Doku[329]lilově knize Teorie odvozování slov;[10] naznačuje nemalé možnosti užití grafů v tomto jazykovědném oboru. Zaznamenejme, že existuje i dosti složitá aplikace teorie grafů v lexikologii.[11]

Aplikaci teorie grafů ve fonologii se věnovali S. Marcus a E. Vasiliu.[12] Tyto aplikace vlastně patří do analytických modelů jazyka. Sem patří také studium kontextového prostoru jazyka, který je příkladem neorientovaného grafu: uzly jsou fráze jazyka a hrany tvoří právě ty neuspořádané dvojice různých frází, které jsou v kontrastní opozici.[13] Analytické modely jsou takové modely přirozeného jazyka, které vycházejí z předpokladu, že je dána množina všech jeho vět; tu potom analyzují. Významným odvětvím analytických modelů je studium zaměnitelnosti slovních tvarů ve větě a studium morfologických (gramatických) kategorií; jde vlastně o využití orientovaných grafů, jejichž uzly jsou slovní tvary jazyka.[14] Do analytických modelů jazyka lze např. zařadit i autorův model větného rozboru, který hlouběji propracoval I. I. Revzin; uzly grafu tvoří slovní tvary věty a hrany, které se postupně konstruují, modelují závislostní vztah.[15] Za zmínku stojí, že z metod analytických modelů těží i aplikace grafů při rozboru literárních děl (včetně dramat), kterým se věnují někteří rumunští vědci.[16]

Bohaté impulsy pro aplikaci grafů vycházejí z generativních gramatik.[17] Ústředním pojmem je zde vlastně frázový ukazatel, který — jak vyplývá již z Holtovy práce[18] — je vhodným objektem hlubšího matematického studia. Frázový ukazatel je pojmem složkové syntaxe; jeho základem je speciální případ orientovaného grafu — vrcholový strom. S aplikací vrcholového stromu se setkáváme i v závislostní syntaxi;[19] zde je často spjat se studiem větné projektivity.[20]

Uvedli jsme některé případy aplikace grafů v lingvistice. Význam teorie grafů pro lingvistiku není však jen v počtu takových případů, ale také v tom, že otázky, které si teorie grafů klade, mohou být inspirující i pro studium jazykových struktur. Zisk ovšem může být oboustranný. Všimneme si některých významnějších problémových okruhů teorie grafů a upozorníme na jejich vztah k lingvistice.

Vnitřně stabilní množinou uzlů orientovaného grafu se rozumí taková množina uzlů, kde žádné [330]dva uzly, které do ní patří, nespojuje hrana. Vnějškově stabilní množinou se rozumí taková množina uzlů orientovaného grafu, že z každého uzlu, který do ní nepatří, vede hrana k některému uzlu, který do ní patří. Množina uzlů, která je vnitřně a vnějškově stabilní, se nazývá jádro grafu. Na možnosti aplikace těchto pojmů v lingvistice upozornil Marcus (o. c. v pozn. 8). Především si všímal jádra grafu, jehož uzly jsou fonémy, resp. některé gramatémy rumunštiny a v němž uspořádaná dvojice xy tvoří hranu, právě když v alespoň jednom případě stojí v rumunštině jednotky x a y bezprostředně za sebou (srov. statě cit. v pozn. 12). Kdybychom zkonstruovali podobný graf pro fonémy v češtině, zjistili bychom například, že {b, p} a {d, t} jsou vnitřně stabilní množiny.

Obarveným grafem se v teorii neorientovaných grafů rozumí graf, jehož každému uzlu se přisoudí nějaká barva tak, aby kterékoli dva uzly spojené hranou byly obarveny různě. Teorie grafů si především klade otázku po obarvení jednotlivých grafů nejmenším počtem barev; tato otázka míří k složitým problémům (známá je dosud nedokázaná hypotéza, že každý rovinný graf lze obarvit nejvýše čtyřmi barvami). Položíme-li za uzly grafu hlásky přirozeného jazyka a spojíme-li dvojici hlásek hranou, právě když existuje dvojice významově různých promluv, které se liší právě v jednom výskytu těchto hlásek, vidíme, že otázky konstrukce fonémů souvisí s barvením grafu. Na jiné užití obarvených grafů ve fonologii upozornil Marcus (o. c. v pozn. 8). Zcela odlišným způsobem aplikoval obarvené grafy v lingvistice Čulík, když studoval matematické vlastnosti vzájemného překladu lexikálních jednotek několika jazyků.[21]

Dvojdílným grafem se rozumí neorientovaný graf, jehož množinu uzlů lze rozložit do dvou disjunktních množin X a Y tak, že o libovolné hraně platí, že spojuje některý uzel z množiny X s některým uzlem z množiny Y. Dvojdílné grafy se někdy nazývají dvojbarevné, protože jsou to právě ty, které lze obarvit dvěma barvami (z jiného důvodu se jim také říká sudé grafy). Vlastnosti dvojdílných grafů jsou dosti soustavně studovány. Jestliže jednu množinu uzlů v dvojdílném grafu považujeme za množinu jazykových forem některého druhu a druhou množinu uzlů za množinu jazykových funkcí odpovídajícího druhu a jestliže formu p spojíme hranou s funkcí q, právě když q může mít formu p, dostaneme výrazné lingvistické využití dvojdílného grafu. Takový graf umožňuje podrobné studium formálních vlastností homonymie a synonymie jazykových jednotek.

Kreslení grafu v rovině je dosti běžným, výrazově úsporným prostředkem, je však také pramenem obecných otázek, především otázky, zda graf je rovinný; ta je spjata se závažnými teorémy. V případě, že závislostní strukturu věty vyjádříme vrcholovým stromem se slovosledně uspořádanými uzly, lze otázku, zda struktura věty je projektivní, zodpovědět odvoláním na geometrické vlastnosti jisté rovinné reprezentace této věty.[22] Autor ukázal, že struktuře věty lze přiřadit neorientovaný graf, o němž platí, že je rovinný, právě když je věta projektivní.[23] Ukazuje se tedy, že významná otázka závislostní syntaxe může být zodpovězena odvoláním na přirozenou otázku teorie grafů.

V posledních letech se v teorii grafů studují otázky rekonstrukce grafu ze seznamu jeho podgrafů jistého druhu; o grafu se předpokládá, že nemá pojmenovány uzly, jde tedy vlastně o rekonstrukci tvaru grafu z tvaru podgrafů. Obecně jsou tyto otázky velmi obtížné a byly vyřešeny jen pro některé speciální typy grafů. Nejzávažnější výsledky byly získány pro stromy.[24] Protože struktura věty se často popisuje pomocí vrcholového stromu, jehož uzly jsou ohodnoceny gramatickými kategoriemi nebo větnými členy, zdá se být rozumné uvažovat o přenesení těchto otázek do lingvistiky, tj. uvažovat o rekonstrukci struktury věty ze struktury některých frází, které [331]jsou ve větě obsaženy. Zkušenosti z teorie grafů ukazují, že řešení těchto problémů vede k hlubšímu objasnění stavby rekonstruovaných objektů.

Do teorie grafů pronikají impulsy, jejichž původ je vlastně lingvistický. Vznikají formální gramatiky generující množiny grafů; graf zde tedy vlastně přejímá úlohu věty.[25] S tímto proudem souvisí jiný, který míří do lingvistiky; v něm jde o gramatiky, které generují stromové struktury vět.[26]

Závěr: Pro využití grafů jsou v lingvistice velké možnosti. Jak jsem se pokusil ukázat, grafy mohou pomoci jak při přesné a názorné formulaci problémů, tak i při jejich řešení. V řadě prací již také byla teorie grafů významněji využita, nejsoustavněji při popisu větné struktury. Dosažené výsledky naznačují, že otázky, které se v teorii grafů kladou a řeší, mohou přispět i k hlubšímu pochopení struktury různých jazykových jevů.

Slovo a slovesnost, ročník 33 (1972), číslo 4, s. 328-331

Předchozí Jan Lehár: Úvahy o dvou staročeských básních

Následující Josef Štěpán: Pozoruhodná sovětská práce o podřadném souvětí