Fák

Feladat: Legyen G egy tetszõleges gráf és e egy éle. Bizonyítsuk be, hogy a következõk ekvivalensek:

• e egyetlen körben sem szerepel,
• e elhagyásával a komponensszám növekedik,
• e elhagyásával a komponensszám eggyel növekedik,
• G csúcsai két osztályba sorolhatók úgy, hogy e legyen az egyetlen él, amely két végpontja különbözõ osztályba esik.

Feladat: Lehetnek-e a következõ sorozatok egy fa fokszámsorozata?

• 3,3,2,2,1,1,1,1,
• 3,3,2,2,2,2,1,1.

Definíció: Egy fa v csúcsa levél, ha foka 1.

Feladat: Egy n pontú fának hány levele lehet?

Feladat: Egy n pontú fa minden fokszáma 3 vagy 1. Hány levele van?

Feladat: Egy fa minden nem levél csúcsának legalább 3 a foka. Mi a leveleinek minimális száma?

Feladat: Bizonyítsuk be, hogy egy F gráfra a következõk ekvivalensek:

• F fa,
• F-nek eggyel kevesebb éle van mint csúcsa és összefüggõ,
• F-nek eggyel kevesebb éle van mint csúcsa és körmentes,

Feladat: Hány éle van egy n pontú, c komponensû körmentes gráfnak?

Feladat: Tudjuk, hogy egy T fa felépíthetõ ághajtásokkal. Bizonyítsuk be, hogy T bármelyik csúcsa kiválasztható a felépítés kiinduló csúcsának.

Feladat: Legyen T egy páros élû fa. Bizonyítsuk be, hog T élei párokba állíthatók úgy, hogy minden pár két éle összefut (azaz van közös végpontjuk, szomszédosak).

Feladat: Legyen T egy fa, amely élszáma hárommal osztható. Igaz-e, hogy élei hármas csoportokba oszthatók úgy, hogy minden csoport egy összefüggõ élhármast alkosson? Adjunk szükséges és elégséges feltételt ilyen felbontás létezésére.

Feladat: Bizonyítsuk be, hogy egy fában található olyan csúcs, amely az összes leghosszabb úton rajta van.

Feladat: Legyen T₁,T₂,T₃,...,T_k egy fa összefüggõ részgráfjai úgy, hogy tetszõleges két részgráfnak legyen közös pontja. Bizonyítsuk be, hogy ekkor az összes részgráfnak van közös pontja.

Feladat: ^* Egy n x n-es táblázat n² mezõjében karaktereket írunk úgy, hogy semelyik két sor se legyen ugyanaz (legalább egy pozícióban különbözzenek). Bizonyítsuk be, hogy letakarható a táblázatunk egy oszlopa úgy, hogy a látható része a táblázatnak továbbra is rendelkezzék ezzel a tulajdonsággal.  

Definíció: Egy T fát egy r kitüntetett csúcsával gyökeres fának nevezzük. r a gyökeres fa gyökere.

Megjegyzés: Egy gyökeres fában minden csúcs fontos paramétere a gyökértõl vett távolsága. A gyökértõl i távolságra lévõ csúcsok halmazát az i-edik generációnak nevezzük. r az egyetlen 0-dik generációs csúcs. A gyökeres fák lerajzolása úgy történik, hogy a csúcsok egymás alatt lévõ vizszintes (e₀, e₁, e₂, ...) egyenesekre kerüljenek. Az i-edik generáció az i indexû egyenesre kerüljön.

Feladat: i>0 esetén minden i-edik v generációs csúcsnak egyetlen i-1-edik generációs szomszédja van. Az összes többi szomszédja i+1-edik generációs.

Definíció: A fenti feladat v csúcsának i-1-edik generációs szomszédját v apjának nevezzük. A v csúcs i+1-edik generációs szomszédait v fiainak nevezzük. A gyökeret õsapának is nevezzük.

Definíció: Egy gyökeres fa levele egy fiú nélküli csúcs. Vigyázat, ha egy (T,r) gyökeres fa gyökerének egyetlen fia van, akkor T-t faként tekintve r egy levele (1 a foka), gyökeres faként tekintve r nem levél (van fia).

Feladat: Egy gyökeres fa csúcsaihoz rendeljük az apjukhoz vezetõ élt. Mi ennek a hozzárendelésnek/függvénynek az értelmezési tartománya és mi a függvényértékek halmaza? Bizonyítsuk be, hogy 1-1-értelmû függvényt definiáltunk. Mi következik ebbõl?

Feladat: Egy bináris fa egy olyan gyökeres fa, amely minden nem levél csúcsának két fia van. Bizonyítsuk be, hogy egy bináris fának eggyel több levele van mint nem levél csúcsa.

Definíció: Ha egy gyökeres fa minden csúcsára ennek fiai közt egy sorrendet rögzítünk, akkor ezt gyökeres síkfának nevezzük. A geometriai sík jelzõ onnan ered, hogy a síkfák lerajzolását úgy végezzük, hogy egy csúcs fiainal a balról jobbra sorrend adja a fenti sorrendet. Azaz a sorrend a geometriai elhelyezekedésbõl kiolvasható legyen. Bináris síkfáknál minden nem levél csúcsnál két fiú van, amelyeket sorbaraktunk: az elsõ fiúra a balként, a másodikra a jobbként hívatkozunk.

Feladat: ^* Legyen T egy bináris síkfa. Legyen u egy csúcsa, amelynek két fia v és v_jobb. v két fia legyen w_bal és w_jobb. T-n definiáljuk a következõ billentésnek nevezett operációt: u új két fia w_bal és v, amelynek bal fia w_jobb és jobb fia v_jobb. Legyen T és T' két tetszõleges n levelû bináris síkfa. Bizonyítsuk be, hogy T' megkapható T-bõl billentések sorozatával.  

Feladat: Legyen G egy összefüggõ gráf. A következõ eljárással G éleinek a piros és zöld színek egyikét adjuk:

• G-nek kiválasztjuk egy színezetlen élét: e-t,
• Van-e olyan e-t tartalmazó köre G-nek, amely minden éle színezetlen vagy zöld? Ha igen, akkor e színe legyen piros. Ha nem, akkor e színe legyen zöld.
• Ha minden él színezett leállunk, ha nem, akkor elõrõl kezdjük lépéseinket.

Feladat: A következõ pontok mindegyikében egy összefüggõ gráfot írunk le. Soroljuk fel a leírt gráf összes feszítõfáját.

• C₁₀ a 10 hosszú kör,
• egy kocka csúcsai és élei által alkotott gráf,
• Legyen W_n az az egyszerû gráf, amit úgy kapunk egy 5 hosszú körbõl, hogy egy új csúcsot adunk hozzá, amelyet körünk összes csúcsával összekötünk,

Feladat: Egy teljes gráf csúcshalmaza legyen {1,2,3,...,n}. Az ij él súlya legyen i+j. Határozzuk meg a legnagyobb súlyú feszítõfát.

Feladat: Egy d-dimenziós hiperkocka csúcsai d hosszú 0-1 sorozatok. Két csúcs akkor és csak akkor van összekötve, ha a megfelelõ két sorozat egyetlen pozícióban különbözik (ahol is az egyik csúcsban/sorozatban 0, a másikban 1 áll). Egy élnek legyen i a súlya, ha a két végpontnak megfelelõ sorozat az i-edik pozícióban tér el. Határozzuk meg a legnagyobb súlyú feszítõfa súlyát.

Feladat: Egy él-súlyozott összefüggõ gráf élein az összes súly különbözõ. Bizonyítsuk, hogy egyetlen feszítõfa lesz, amely maximális súlyú lesz.

Feladat: Egy él-súlyozott összefüggõ gráf élein a súlyok olyanok, hogy a maximális súlyú feszítõfa nem egyértelmû. Legyen T egy maximális súlyú feszítõfa. Bizonyítsuk be, hogy az élek súly-rendezett sorrendje megválasztható úgy, hogy a mohó algoritmus T adja outputként.

Feladat: Adjunk meg egy él-súlyozott összefüggõ gráfot úgy, hogy az élein az összes súly különbözõ legyen, de a második legnagyobb súlyú feszítõfa ne legyen egyértelmû.

Feladat: Egy él-súlyozott összefüggõ gráf élein az összes súly különbözõ. Tudjuk, hogy egyetlen T feszítõfánk van, amely maximális súlyú. Legyen T' egy második legnagyobb súlyú feszítõfa. Bizonyítsuk be T' megkapható T-bõl egy él eldobásával és egy új él hozzáadásával.