dalaman airport transfers
Časopis Slovo a slovesnost
en cz

Užití grafů v lingvistice

Ladislav Nebeský

[Discussion]

(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ů.


[1] D. König, Theorie der endlichen und unendlichen Graphen, Leipzig 1936.

[2] Např. C. Berge, Théorie des graphes et ses applications, Paris 1958; O. Ore, Theory of Graphs, Amer. Math. Soc., Providence 1962; A. A. Zykov, Teorija konečnych grafov, Novosibirsk 1969; F. Harary, Graph Theory, Reading, Mass. 1969.

[3] J. Sedláček, Kombinatorika v teorii a praxi (Úvod do teorie grafů), Praha 1964.

[4] K. Čulík — V. Doležal — M. Fiedler, Kombinatorická analýza v praxi, Praha 1967.

[5] V literatuře lze ovšem nalézt různé neekvivalentní definice grafu. Např. někteří autoři u neorientovaných grafů připouštějí smyčky, tj. hrany spojující uzel se sebou samým.

[6] Teorii rovinných grafů je věnována kniha O. Orea The Four Color Problem, New York 1967.

[7] N. Goodman, Graphs for Linguistics, ve sb. Structure of Language and Its Mathematical Aspects, PSAM 12, Amer. Math. Soc., Providence 1961, s. 51—55; srov. P. Novák, Struktura jazyka a její matematické aspekty, SaS 25, 1964, 139—144.

[8] S. Marcus, Teorija grafov, lingvističeskije oppoziciji i invariantnaja struktura, ve sb. Problemy strukturnoj lingvistiky, Moskva 1962, s. 22—30.

[9] E. Zierer, The Theory of Graphs in Linguistics, The Hague 1970; srov. mou rec. v SaS 33, 1972, 260—261.

[10] M. Dokulil, (Tvoření slov v češtině I) Teorie odvozování slov, Praha 1962, s. 13.

[11] Viz A. Rapoport — A. Rapoport — W. P. Livant — J. Boyd, A study of lexical graphs, Foundations of Language 2, 1966, 338—376. (Lexikálním grafem rozumějí autoři graf, jehož uzly jsou slova; hrany jsou konstruovány podle různých kritérií založených na významové příbuznosti. V práci se vyšetřují statistické vlastnosti některých lexikálních grafů získaných experimentální cestou.)

[12] S. Marcus — E. Vasiliu, Mathématiques et phonologie. Théorie des graphes et consonantisme de la langue roumaine I, Revue roumaine de mathématiques pures et appliquées 5, 1960, 319—340; titíž, Mathématiques et phonologie. Théorie des graphes et consonantisme de la langue roumaine II, tamtéž, s. 681—704; E. Vasiliu, Mathematica şi fonologie. Theoria grafelor şi consonantismul limbii române, Fonetica şi Dialectologie 3, 1962, 15—55.

[13] Viz např. S. Marcus, Algebraické modely v lingvistice, Praha 1969, především s. 43—48. Marcus zde neužívá terminologie teorie neorientovaných grafů, ale terminologie obecnější teorie metrických prostorů.

[14] Viz např. K. Rajskij, Grafy i morfologičeskije kategoriji v algebraičeskoj lingvistike, Bulletin Mathématique de la Société des Scientes Mathématiques de la République socialiste de Roumanie 12, 1968, 111—128.

[15] Viz L. Nebeský, O jedné formalizaci větného rozboru, SaS 23, 1962, 104—107; I. I. Revzin, Grammatičeskij analiz čerez sistemu podfraz, Naučno-techničeskaja informacija, Serija 2, 1967, č. 8, s. 27—31.

[16] Viz zejm. S. Marcus, Poetica matematică, Bucureşti 1970, hlavně kap. 5, 7 a 8.

[17] Viz např. K. Čulík, Applications of Graphs Theory to Mathematical Logic and Linguistics, Theory of Graphs and Its Applications, Praha 1964, s. 13—20; týž, On the Ordered Rooted Trees Used in Theory of Languages, Théorie des graphes, Paris 1967, s. 69—76.

[18] A. W. Holt, A Mathematical and Applied Investigation of Tree Structures for Computer Syntactic Analysis, A dissertation in the Department of Linguistics, Pensylvannia 1963 (rozmnoženo).

[19] Neformálně užívá grafů V. Šmilauer, Učebnice větného rozboru, Praha 1958.

[20] O matematických vlastnostech větné projektivity za předpokladu, že větná struktura je popsána závislostním stromem, viz např. L. Nebeský, Algebraic Properties of Trees (Postscript P. Novák), Acta UK, Praha 1969, kap. 4; srov. týž, Některé otázky závislostní koncepce syntaxe, SaS 32, 1961, 20—25. O projektivitě obecněji viz např. S. Marcus, Algebraic Linguistics; Analytical Models, New York 1967, kap. 6.

[21] K. Čulík, Ispoľzovanije abstraktnoj semantiky i teoriji grafov v mnogojazyčnych perevodnych slovarjach, Problemy kibernetiki 13, 1965, 221—232.

[22] Viz např. S. Marcus, o. c. v pozn. 20, s. 237—240. Srov. i L. Uhlířová, On the Non-Projective Constructions in Czech, Prague Studies in Mathematical Linguistics 3, Praha 1972, s. 171 až 181.

[23] L. Nebeský, A Planar Test of Linguistic Projectivity, Kybernetika 8, 1972, 351—354.

[24] Viz např. B. Manvel, Reconstructions of Trees, Canadian Journal of Mathematics 22, 1970, 55—60.

[25] Viz např. U. G. Montanari, Separable Graphs, Planar Graphs and Web Grammars, Information and Control 10, 1970, 243—267 a T. Pavlidis, Linear and Contect-free Graph Grammars, Journal of the Association for Computing Machinery 19, 1972, 11—22.

[26] Viz A. V. Gladkij — I. A. Meľčuk, Tree Grammars (Δ-grammars), International Conference on Computational Linguistics, Preprint No. 1, Sanga Säby 1969.

Slovo a slovesnost, volume 33 (1972), number 4, pp. 328-331

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

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