NE

Értelmetlen/véletlen mondatok:

• A Permutáció a lehetséges sorbaállításokat és azok számát adja meg.

  A mondat nyelvileg és matematikailag értelmetlen. Az viszont tetszett, hogy a hallgató a permutáció fogalmát annyira becsüli, hogy nagy betűvel írja. Erre azonban nem adok külön pontot.

• Egy H halmaz párosítás, ha p:H->H bijekció.
• P párosítás azoknak a pontoknak a halmaza, amik P-re illeszkednek.
• A halmaz fölött értelmezem a természetes számok sorozatát, amely egy sorbarendezést biztosít a halmaz elemei között.
• A gráf v₁e₁v₂e₂... v_ne_n sorozat elemeinek összessége.
• Egy párosítás, ha minden elemhez ugyanannyi elemet rendelünk hozzá.
• Egy S halmaz feletti M multihalmaznak nevezzük a valós számok egy függvényét.
• Összefüggőnek nevezük a gráfot, ha bármely élet elhagyva a gráf nem bomlik két gráfra, tehát minden pontjához el lehet jutni.
• Elérhetőség relációról beszélünk, ha a gráf bármely két csúcs között van út.
• Ha G fokszáma páratlan, akkor nincs benne Kőnig-akadály.
• Egy S véges halmaz feletti multihalmaz felveszi az S-ben lévő természetes számokat.
• Legyen M multihalmaz H felett, ekkor az M multihalmaz egy természetes számokat felvevő függvényt értünk.
• Egy gráf egy (V,E,I) hármas. V egy végtelen halmaz, a csúcsok halmaza. E egy véges halmaz, az élek halmaza. I egy illeszkedési reláció V és E között.

  Emlékezhetünk, hogy a véges/végtelen halmazok szerepeltetéséről a félév során többször beszéltem. A kombinatorika központi fogalmaiban véges halmazok szerepelnek. Ha ezt nem jegyeztük meg, akkor ne írjunk a végesség illetve végtelenségről. Ha mégis írunk, akkor kötelezzük el magunkat. Az gyávaság, hogy V legyen végtelen, E legyen véges és ha utólag tudom melyik a korrekt, akkor csak egy véletlen elírást kell kimagyaráznom (esetleges kettő helyett). Mellesleg a fenti definíció a véges halmazokra való hivatkozás esetén is erősen hiányos lenne (lásd alább).

• Egy S halmaz feletti multihalmaz egy S-en értelmezett S feletti természetes számokat felvevő függvény.

  "S feletti" jelző a multihalmazok egy "szlengje". A függvénytan szlengjébe ne keverjük bele. Egy S halmaz feletti multihalmaz egy S-en értelmezett, természetes számokat felvevő függvény.

• Egy párosítás, ha H minden eleméhez hozzárendelünk H' egy elemét.

  Bizonyos szavak ismétlődően visszatérhetnek a félév során, de teljesen más környezetben. Két halmaz közötti párbaállító leképezés; páros permutáció; párosítás egy gráfban; páros gráf mind egy-egy fogalom. Mindegyik kötödik az óvodában megtanult páros szám fogalmazához. Mégis más és más fogalmakról van szó. Itt talán a párbaállító leképezés fogalmát szerette volna a a hallgató leírni a párosítás fogalmának kérdésere. A párbaállító leképezést se jól írta le.

• Legyen S egy véges halmaz. M egy multihalmaz H felett, ha M:S->N.

  Az alaphalmaz egy halmaz, angolul set. Általában H és S betűket használom jelölésére. Lehet, hogy előadáson S feletti multihalmazt definiáltam, a vizsgán H feletti multihalmazt kérdezem (vagy fordítva). Ha megértettük a definíciót, akkor könnyű a másik jelölésre átírni. Ha úgy érezzuk, hogy nem megy akkor írjuk le az S feletti multihalmaz fogalmát akkor is ha én a H felettire kérdezek rá. Ez is jobb mintha a H és S jelölés keveredik.

• Egy gráf összefüggő ha bármely két csúcs között van ~ reláció.

  A relációnak van egy alaphalmaza. Az alaphalmaz két eleme vagy relációban áll vagy nem. Egy nyelvileg helyes mondat: Egy gráf összefüggő, ha bármely két csúcsa ~ relációban áll. A fenti mondat nem teljes definíció mert a ~ reláció fogalmát használja. A teljességhez a ~/elérhetőség relációt is fel kell írni (akkor is ha külön nem kérdeztem). Azaz ~ egy reláció a gráf csúcsain: u~v pontosan akkor, ha gráfunkban van uv út. Egyszerűbb összevontan leírni a definíciót: Egy gráf összefüggő, ha bármely két csúcsa között van út. Most már látszik is, hogy emlékeztünk valamire. Igazából két dologra is. Ezek keverése arra utal, hogy a kapcsolódó "nyelvek" egyikét sem sajátítottuk el jól.

• A gráfok fokszámai páros./A gráfok fokszámának összege páros.

  FONTOS: Egy gráf csúcsai esetén beszélhetünk fokszámról. Egy konkrét 10 pontú gráfban 10 fokszám írható fel. Egy helyes megfogalmazás: Tetszőleges gráfban a fokszámokat összeadva páros számot kapunk.

• Egy sétát vonalnak nevezünk, ha minden él csak egyszer szerepel benne.

  Mit értünk az alatt, hogy "csak egyszer"? Egyszer, de nem többször? Az nem jó. Egy helyes megfogalmazás: Egy sétát vonalnak nevezünk, ha minden él legfeljebb egyszer szerepel benne.

• Egy gráf fa ha minden élét elhagyva nem összefüggővé válik.

  Minden élét hagyjuk el? Valóban? Akkor maradnak a pontok és nem lesz él. Ha legalább kettő csúcs van, akkor a maradék már nem összefüggő gráf.

• Egy gráf fa ha bármely élét elhagyva nem összefüggővé válik./ Egy gráf fa ha bármely élét elhagyva elveszti összefüggőségét.

  Ez már majdnem jó. Nem összefüggővé válik/elveszti összefüggőségét sugallja, hogy eredetileg összefüggő volt. Ne sugalljunk, feltételeinket mondjuk ki egyértelműen. Egy helyes megoldás: Egy gráf pontosan akkor fa, ha összefüggő és bármely élét elhagyva elveszti összefüggőségét.

• Egy gráf fokszámának összege páros.

  Egy gráfnak van fokszáma? Nincs. Ha lenne, akkor minek összeadás (ahhoz jó lenne több szám). Egy gráfnak nincs fokszáma. A gráf csúcsainak van fokszáma. Általában több csúcs van egy gráfban és mindegyikhez tartozik egy fokszám. Ezek összege valóban páros. Egy helyes megfogalmazás: Egy gráf fokszámait összeadva páros számot kapunk.

• Egy séta csúcsainak nem ismétlődését útnak nevezzük.

  Mit nevezünk útnak? Valaminek a nem ismétlődését? Az bonyolult lenne. Egy helyes meghatározás: Ha egy séta csúcsai közt nincs ismétlődés, akkor a sétát útnak nevezzük.

• Egy gráf fokszámainak összege a gráf élszámainak kétszeresével egyenlő.

  Egy gráfnak van élhalmaza. Érdekes esetben több éle van a gráfnak. Élszáma (élhalmazának elemszáma) azonban egy van. Egy helyesen megfogalmazott állítás: Egy gráf fokszámainak összege a gráf élszámának kétszeresével egyenlő. Csak viccként: Ha több élszám lenne, akkor melyik duplájával lenne egyenlő a fokok összege?

• G összefüggő, ha minden csúcsa között van út.

  Ha a "között" névutót hely meghatározásra használjuk, akkor kettő/több helyet kell megadnunk. Esetünkben egy korrekt definíció: G összefüggő, ha bármely két csúcsa között van út.

• Ha M egy párosítás és L egy lefogó halmaz, akkor M > L.

  M egy élhalmaz, L egy csúcshalmaz. M és L értelmes összehasonlítása nagyon kérdéses. Elemszámuk összehasonlítható (a reláció nem az, amit látunk!)

• Egy gráfban a fokok összege 2E.

  Egy csúcs foka egy természetes szám, Természetes számok össege egy természetes szám. E egy halmaz (gráf éleinek halmaza). E/ általában egy halmaz kétszeresének nincs értelme. Helyesen: Egy gráfban a fokok összege 2|E|.

• A vizsgált optimalizálási probléma: |max{M: M párosítás G-ben}| / A vizsgált optimalizálásai probléma: max|{M: M párosítás G-ben}|

  Mi is az optimalizálási probléma? A párosítások között a maximális elemszám meghatározása. Formulával: A vizsgált optimalizálási probléma: max{|M|: M párosítás G-ben}. Házi feladat: Értelmesek-e a fenti kiollózott mondatok? Ha igen, akkor mi az értelmük?

• A párosításokal kapcsolatos optimalizálási probléma: a legnagyobb párosítás megkeresése.

  Egy párosítás az egy élhalmaz. Halmazok összehasonlítása kérdéses. Mikor nagyobb egy halmaz a másiknál? Elemszáma több? Tartalmazza a másikat? Ha megállapodunk a legnagyobb fogalmában általában több legnagyobb párosítást találunk. Egy helyes válasz: A párosításokal kapcsolatos optimalizálási probléma: az egyik legnagyobb elemszámú párosítás megkeresése.

• omega(G) a G gráf legnagyobb klikkje.

  Mint előbb a legnagyobbat tisztázni kell. omega(G) egy a G gráfhoz rendelt paraméter, egy természetes szám. Nem egy klikk. Egy helyes megoldás: omega(G) a G gráf legnagyobb elemszámú klikkjének mérete. Egy másik tömör lehetőség: omega(G) a G gráf maximális klikkmérete.

• A mohó algoritmus legfeljebb akkora mint a legnagyobb fokszám +1.

  A lenagyobb fokszám + 1 egy természetes szám. Összehasonlítható egy másik természetes számmal. De nem egy algoritmussal. Egy helyes megfogalmazás: A mohó algoritmus által kiszámolt színezés által felhasznált színek száma legfeljebb akkora mint a legnagyobb fokszám +1.

• Egy gráf fokszámán a gráf nem hurokéleinek számának és hurokélei számának kétszeresének összegét értjük.

  Újra és újra: Egy gráfnak nincs fokszáma, minden csúcsának van egy-egy fokszáma. A helyes fogalom: Egy gráf v csúcsának fokszámán a gráf v-re illeszkedő nem hurokéleinek számának és v-re illeszkedő hurokélei számának kétszeresének összegét értjük.

• Séta, út definíciója korrektül, majd: A kör olyan út, ahol v₀=v_k és k>0.

  Egy út olyan séta, amelyben nincs csúcsismétlődés. Speciálisan v₀ és v_k (k>0) szükségszerűen különbözik. Azaz a körök szükségszerűen nem utak. Egy helyes megfogalmazás (ami talán tisztázza az úthoz való szoros kapcsoatot is): v₀e₁ v₁e₂ ... v_n-1e_n v_n séta pontosan akkor kör, ha n>0, v₀e₁ v₁e₂ ... v_n-2e_n-1 v_n-1 út, továbbá e_n egy új él, ami záródóvá teszi a sétát, azaz v₀=v_n.

• Egy k elemű M multihalmaz sorbaállítása olyan k hosszú sorozat, ahol az M(s) elem M(s)-szer ismétlődik.

  Mik szerepelnek a sorozatban? M(s) az s elem multiplicitása, egy természetes szám. Ez nem lesz a sorozatban. Azon S halmaz elemei szerepelhetnek, ami feltti multihalmazzal dolgozunk, azaz a "válasz s betűje". Egy korrekt lehetőség: Egy k elemű M multihalmaz (S felett) sorbaállítása olyan k hosszú sorozat S elemeiből, ahol minden s (S egy eleme) M(s)-szer ismétlődik.

• Egy G gráf egy (V,E,I) hármas, ahol V, E véges halmazok és I egy illeszkedési reláció V és I között (azaz VxE Descart-szorzat egy részhalmaza).

  Ez lehetne egy geometria is (pontok, egyenesek, illeszkedés). A gráf LÉNYEGE, hogy minden élre két csúcs illszekedik (a két illeszkedő csúcs egybeesése lehetséges).

• Egy séta egy v₀e₁ v₁e₂ ... v_n-1e_n v_n sorozat, ahol v₀, v₁, ..., v_n csúcsok és e₁, e₂, ..., e_n élek.

  Csak egy csúcs-él-csúcs-él-csúcs-... sorozat? Na nem! A lényeg: minden él az ő két végpontja között van!

• Ha M egy k elemű multihalmaz, akkor sorbaállítása egy k hosszú sorozat.

  Mik a sorozat elemei, milyen feltétel van rá a hosszon kívül? Egy helyes megoldás: Ha M egy k elemű multihalmaz H felett, akkor sorbaállítása egy k hosszú sorozat H elemeiből, amelyre teljesül, hogy h (H egy eleme) pontosan M(h)-szor szerepel benne.

• Legyen N a természetes számok halmaza. ...

  Bőbeszédű. A természetes számok jelölése standard. Visszamenni az ősrobbanásig felesleges.

• M élhalmaz párosítás, ha |V(M)|=2|M|.

  Szükszavú. Definiáljuk egy M élhalmaz esetén V(M)-et. Anélkül a fenti (korrekt) definíció hiányos.

• Jó színezésről beszélünk, ha a szomszédos csúcsok különböző színűek.

  Szűkszavú. Írjuk le, hogy csúcsoknak adunk színeket. Kitalálható, de ne az én fantáziámra építsenek. Egy korrekt megoldás: Egy gráf jó színezése alatt azt értjük, hogy csúcsaihoz színeket rendelünk úgy, hogy a szomszédos csúcsok különböző színt kapjanak.

• Kérdés: Definiálja a permutáció fogalmát. Válasz: Egy H halmaz permutációja egy p:H->H bijekció. H permutációinak halmazát S(H)-val jelöljük. |S(H)|=n!. Ha egy n elemű halmaznak s_n permutációja van, akkor s_n=ns_n-1.

  Bőbeszédű. Ha olyanokat ír, amit nem kérdezek, azért nem jár plusz pont.

• Egy gráf fa ha, összefüggő és bármely élet elhagyva megszűnik összefüggősége. Továbbá egy gráfot akkor nevezünk fának, ha bármely két csúcsa között pontosan egy él halad.

  Bőbeszédű. Ha az első mondat után leállunk, akkor tökéletes definícióját adjuk a fának. A második mondat mindent elront. Sokan az "bármely két csúcs között pontosan egy út halad" definíciót szokták a fenti módon leírni. Úttal, illetve éllel összekötöttség két különböző dolog.

• Egy gráf fa ha, összefüggő és bármely élet elhagyva megszűnik összefüggősége. Továbbá egy gráfot akkor nevezünk fának, ha összefüggő és nincs benne hurokél.

  Bőbeszédű. Ha az első mondat után leállunk, akkor tökéletes definícióját adjuk a fának. A második mondat mindent elront. Sokan az "összefüggő és nincs benne kör" definíciót szokták a fenti módon leírni. A kör és hurokél két különböző dolog. A hurok élek felfoghatók mint egy 1 hosszú kör. Ezek tiltása nem elég a fa mivolthoz.

• Feladat: ... Számoljuk ki a sorozat első hét elemét. Válasz: a₀=..., a₁=..., a₂=..., a₃=..., a₄=..., a₅=..., a₆=..., a₇=...

  Bőbeszédű. A válasz nyolc elemet ad meg, én csak hetet kértem. Tapasztalat: "Csak" kb 25%-a a vizsgázoknak néhány/kevés 100-as nagyságrendű számokat érintő számolós feladatot is elszámol. De kb 75%-a a vizsgázoknak ezres számokat érintő számolós feladatot elszámol. Altalában úgy lövöm be az ilyen kérdéseket, hogy a₆ nagyságrendje "néhány száz", a₇ nagyságrendje több.

• Feladat: Definiálja a párosítás és lefogó ponthalmaz fogalmát. Milyen optimalizálási feladat kapcsolódik hozzájuk? Válasz: ... nu(G)=max{|M|: M párosítás}, tau(G)=min{|L|: lefogó ponthalmaz}, nu(G)>₌ tau(G).

  Bőbeszédű. Minden tökéletes, kivéve az utolsó egyenlőtlenség. Az pont fordítva áll. Hiba (elég durva). Hogy került oda? Én nem kérdeztem!

• Jó színezésnél egy klikk minden csúcsát különböző színűre kell színezi, mert a klikk egy összefüggő részgráfja G-nek.

  Ha valmit nem tudunk indokolni, akkor ne indokoljuk. Egy helyes indoklás: Jó színezésnél egy klikk minden csúcsát különböző színűre kell színezi, mert a klikk bármely két csúcsa összekötött és emiatt a jó színezésnek más-más színt kell adnia.