Matek VI. tétel

Question 1

Gráf fogalma

Answer 1

Egy gráf egy matematikai struktúra, amely csúcsok (vertexek) és az ezeket összekötő élek (élek) halmazából áll

Question 2

Megadási módok

Answer 2

Élszomszédsági mátrix: Egy n x n mátrix, ahol a (i, j)-edik elem a gráfban lévő él súlyát vagy a j. csúcs irányított élét jelöli.

Csúcsszomszédsági lista: Egy lista, amely minden csúcsnak megfelelő szomszédokat tartalmazza.

Question 3

Egyszerű gráf

Answer 3

Minden élből legfeljebb egy van a két csúcs között, és nincs hurokél (él, ami egy csúcsba vezet).

Question 4

Irányítatlan gráf

Answer 4

Az élek nem rendelkeznek iránnyal, tehát a kapcsolat mindkét irányban működik.

Question 5

Irányított gráf

Answer 5

Az élek irányítottak, vagyis a kapcsolat csak az egyik irányba mutat.

Question 6

Séta

Answer 6

Egy sorozat olyan élekből és csúcsokból, ahol minden élt pontosan egyszer használnak fel.

Question 7

Út

Answer 7

Olyan séta, ahol minden csúcsot pontosan egyszer érintenek.

Question 8

Kör

Answer 8

Olyan zárt út, amely egyetlen csúcsot sem érint kétszer (kivéve a kezdő és végpontot).

Question 9

Összefüggőség

Answer 9

Egy gráf összefüggő, ha bármely két csúcsa között van út.

Question 10

Páros gráf

Answer 10

Egy olyan gráf, amely csúcsai két részre oszthatók, és minden él az egyik részbeli csúcsot köti össze a másik részbelivel.

Question 11

Teljes gráf

Answer 11

Minden csúcs között pontosan egy él található.

Question 12

Fa

Answer 12

Összefüggő, körmentes irányítatlan gráf.

Question 13

Kör

Answer 13

Bármely zárt séta vagy út a gráfban.

Question 14

Súlyozott gráf

Answer 14

Az élekhez súlyok vannak rendelve, például számok, amelyek a gráf élein tárolt információkat jelentik.

Question 15

Determinisztikus véges automata

Answer 15

Egy absztrakt matematikai modell, amely véges számú állapotból, átmeneti élekből és egy vagy több elfogadó állapotból áll.

Question 16

Nemdeterminisztikus véges automata

Answer 16

Hasonlóan egy DFA-hoz, de több átmeneti lehetőséggel egy adott állapotból.

Question 17

Reguláris nyelvek

Answer 17

Azok a nyelvek, amelyek kifejezhetők reguláris kifejezések segítségével és felismerhetők reguláris automatákkal.

Question 18

Környezetfüggetlen grammatika

Answer 18

Olyan nyelvtan, amely általánosan használható a nyelvek leírására, amelyeket egy környezetfüggetlen nyelv fogad el.

Question 19

Környezetfüggetlen nyelvek

Answer 19

Azok a nyelvek, amelyeket egy CFG leírhat, és amelyeket elfogad egy környezetfüggetlen automatával.

Question 20

Veremautomata

Answer 20

Olyan absztrakt matematikai modell, amely tartalmaz egy véges szótárat, egy véges vezérlőt, és egy vermet, amelyet az automatikus működés során használnak.