ಟೂರ್ನಮೆಂಟ್ (ಗ್ರಾಫ್ ಥಿಯರಿ)

 

ಟೂರ್ನಮೆಂಟ್ ಡೈರೆಕ್ಟೆಡ್ ಸಂಪೂರ್ಣ ಗ್ರಾಫ್‌ನಲ್ಲಿ ಪ್ರತಿ ಅಂಚಿ(ಎಡ್ಜ್) ಗೆ ದಿಕ್ಕನ್ನು ನಿಯೋಜಿಸುವ ಮೂಲಕ ಪಡೆದ ಡೈರೆಕ್ಟೆಡ್ ಗ್ರಾಫ್ (ಡಿಗ್ರಾಫ್). ಅಂದರೆ, ಇದು ಸಂಪೂರ್ಣ ಗ್ರಾಫ್‌ನ ಓರಿಯೆಂಟೇಶನ್ ಅಥವಾ ಸಮಾನವಾಗಿ ಡೈರೆಕ್ಟೆಡ್ ಗ್ರಾಫ್, ಇದರಲ್ಲಿ ಪ್ರತಿಯೊಂದು ಜೋಡಿ ವಿಭಿನ್ನ ವರ್ಟಿಸಿಸ್ ಗಳನ್ನು ಡೈರೆಕ್ಟೆಡ್ ಅಂಚಿನಿಂದ (ಸಾಮಾನ್ಯವಾಗಿ, ಆರ್ಕ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ) ಎರಡು ಸಂಭವನೀಯ ಓರಿಯೆಂಟೇಶನ್ ಗಳಲ್ಲಿ ಯಾವುದಾದರೂ ಒಂದನ್ನು ಸಂಪರ್ಕಿಸಲಾಗುತ್ತದೆ.

ಟೂರ್ನಮೆಂಟ್ ಗಳ ಅನೇಕ ಪ್ರಮುಖ ಗುಣಲಕ್ಷಣಗಳನ್ನು ಮೊದಲು HG ಲ್ಯಾಂಡೌ ಅವರು Landau (1953) ನಲ್ಲಿ ಕೋಳಿಗಳ ಹಿಂಡುಗಳಲ್ಲಿನ ಪ್ರಾಬಲ್ಯದ ಸಂಬಂಧಗಳನ್ನು ಮಾದರಿಯಾಗಿ ಪರಿಶೀಲಿಸಿದರು. ಟೂರ್ನಮೆಂಟ್ ಗಳ ಪ್ರಸ್ತುತ ಅನ್ವಯಿಕೆಗಳು ಮತದಾನದ ಸಿದ್ಧಾಂತ ಮತ್ತು ಇತರ ವಿಷಯಗಳ ಜೊತೆಗೆ ಸಾಮಾಜಿಕ ಆಯ್ಕೆಯ ಸಿದ್ಧಾಂತವನ್ನು ಒಳಗೊಂಡಿವೆ.

ಟೂರ್ನಮೆಂಟ್ ನ ಹೆಸರು ರೌಂಡ್-ರಾಬಿನ್ ಟೂರ್ನಮೆಂಟ್ ನ ಫಲಿತಾಂಶದಂತಹ ಗ್ರಾಫ್‌ನ ವ್ಯಾಖ್ಯಾನದಿಂದ ಹುಟ್ಟಿಕೊಂಡಿದೆ. ಇದರಲ್ಲಿ ಪ್ರತಿಯೊಬ್ಬ ಆಟಗಾರನು ಪ್ರತಿಯೊಬ್ಬ ಆಟಗಾರನನ್ನು ನಿಖರವಾಗಿ ಒಮ್ಮೆ ಎದುರಿಸುತ್ತಾನೆ ಮತ್ತು ಯಾವುದೇ ಡ್ರಾಗಳು ಸಂಭವಿಸುವುದಿಲ್ಲ. ಪಂದ್ಯಾವಳಿಯ ಡಿಗ್ರಾಫ್ನಲ್ಲಿ, ವರ್ಟೀಸಿಸ್ ಗಳು ಆಟಗಾರರಿಗೆ ಸಂಬಂಧಿಸಿರುತ್ತವೆ. ಪ್ರತಿ ಜೋಡಿ ಆಟಗಾರರ ನಡುವಿನ ಅಂಚು ವಿಜೇತರಿಂದ ಸೋತವರಿಗೆ ಆಧಾರಿತವಾಗಿರುತ್ತದೆ. ಆಟಗಾರನಾಗಿದ್ದರೆ $a$ ಬೀಟ್ಸ್ ಆಟಗಾರ $b$, ನಂತರ ಎಂದು ಹೇಳಲಾಗುತ್ತದೆ $a$ '$b$' ಮೇಲೆ ಪ್ರಾಬಲ್ಯ ಸಾಧಿಸುತ್ತದೆ . ಪ್ರತಿಯೊಬ್ಬ ಆಟಗಾರನು ಅದೇ ಸಂಖ್ಯೆಯ ಇತರ ಆಟಗಾರರನ್ನು ಸೋಲಿಸಿದರೆ ( ಇಂಡಗ್ರಿ = ಔಟ್‌ಡಿಗ್ರಿ ), ಟೂರ್ನಮೆಂಟ್ ಅನ್ನು ನಿಯಮಿತ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ.

ಮಾರ್ಗಗಳು ಮತ್ತು ಸೈಕಲ್ ಗಳು

  ಟೂರ್ನಮೆಂಟ್ ಗಳಲ್ಲಿ ಮತ್ತೊಂದು ಮೂಲಭೂತ ಫಲಿತಾಂಶವೆಂದರೆ ಪ್ರತಿ ಬಲವಾಗಿ ಸಂಪರ್ಕ ಹೊಂದಿದ ಟೂರ್ನಮೆಂಟ್ ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಸೈಕಲ್ ಅನ್ನು ಹೊಂದಿದೆ. [3] ಹೆಚ್ಚು ಬಲವಾಗಿ, ಪ್ರತಿ ಬಲವಾಗಿ ಸಂಪರ್ಕಗೊಂಡ ಪಂದ್ಯಾವಳಿಯು ವರ್ಟೆಕ್ಸ್ ನ ಪ್ಯಾನ್ಸಿಕ್ಲಿಕ್ ಆಗಿದೆ: ಪ್ರತಿ ವರ್ಟೆಕ್ಸ್ ನ $v$, ಮತ್ತು ಪ್ರತಿ $k$ ಟೂರ್ನಮೆಂಟ್ ನಲ್ಲಿ ಮೂರರಿಂದ ವರ್ಟೆಕ್ಸ್ ಗಳ ಸಂಖ್ಯೆಯವರೆಗೆ, ಉದ್ದದ ಸೈಕಲ್ ಯಿದೆ $k$ ಒಳಗೊಂಡಿರುವ $v$ . [4] ಒಂದು ಟೂರ್ನಮೆಂಟ್ $T$ ಇದೆ $k$ ಪ್ರತಿ ಸೆಟ್‌ಗೆ ಬಲವಾಗಿ ಸಂಪರ್ಕಗೊಂಡಿದೆ. $U$ ನ $k-1$ ನ ವರ್ಟೆಕ್ಸ್ ಗಳು $T$, $T-U$ ಬಲವಾಗಿ ಸಂಪರ್ಕ ಹೊಂದಿದೆ. ಟೂರ್ನಮೆಂಟ್ 4-ಬಲವಾಗಿ ಸಂಪರ್ಕಗೊಂಡಿದ್ದರೆ, ಪ್ರತಿ ಜೋಡಿ ವರ್ಟೆಕ್ಸ್ ಗಳನ್ನು ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಪಥದೊಂದಿಗೆ ಸಂಪರ್ಕಿಸಬಹುದು. [5] ಪ್ರತಿ ಸೆಟ್‌ಗೆ $B$ ಹೆಚ್ಚೆಂದರೆ $k-1$ a ನ ಕಮಾನುಗಳು $k$ - ಬಲವಾಗಿ ಸಂಪರ್ಕಗೊಂಡ ಟೂರ್ನಮೆಂಟ್ $T$, ನಾವು ಅದನ್ನು ಹೊಂದಿದ್ದೇವೆ $T-B$ ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಸೈಕಲ್ ಅನ್ನು ಹೊಂದಿದೆ. [6] ಈ ಫಲಿತಾಂಶವನ್ನು Bang-Jensen, Gutin & Yeo (1997) ವಿಸ್ತರಿಸಿದರು.

ಟ್ರಾನ್ಸಿಟಿವಿಟಿ

8 ವರ್ಟಿಸಿಸ್ ಗಳ ಮೇಲೆ ಟ್ರಾನ್ಸಿಟಿವ್ ಪಂದ್ಯಾವಳಿ.

ಇದರಲ್ಲಿ ಒಂದು ಟೂರ್ನಮೆಂಟ್ $((a\rightarrow b)$ ಮತ್ತು $(b\rightarrow c))$$\Rightarrow$$(a\rightarrow c)$ ಟ್ರಾನ್ಸಿಟಿವ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಬೇರೆ ರೀತಿಯಲ್ಲಿ ಹೇಳುವುದಾದರೆ, ಟ್ರಾನ್ಸಿಟಿವ್ ಟೂರ್ನಮೆಂಟ್‌ನಲ್ಲಿ, ವರ್ಟಿಸಿಸ್ ಗಳನ್ನು (ಕಟ್ಟುನಿಟ್ಟಾಗಿ) ಸಂಪೂರ್ಣವಾಗಿ ಅಂಚಿನ ಸಂಬಂಧದಿಂದ ಆದೇಶಿಸಬಹುದು ಮತ್ತು ಅಂಚಿನ ಸಂಬಂಧವು ತಲುಪುವಿಕೆಯಂತೆಯೇ ಇರುತ್ತದೆ.

ಸಮಾನ ಪರಿಸ್ಥಿತಿಗಳು

ಕೆಳಗಿನ ಹೇಳಿಕೆಗಳು ಟೂರ್ನಮೆಂಟ್ ಗೆ ಸಮನಾಗಿರುತ್ತದೆ $T$ ಮೇಲೆ $n$ ಶೃಂಗಗಳು:

1. $T$ ಸಕರ್ಮಕವಾಗಿದೆ.
2. $T$ ಕಟ್ಟುನಿಟ್ಟಾದ ಒಟ್ಟು ಆದೇಶವಾಗಿದೆ.
3. $T$ ಅಸಿಕ್ಲಿಕ್ ಆಗಿದೆ.
4. $T$ ಉದ್ದ 3 ರ ಸೈಕಲ್ ಅನ್ನು ಹೊಂದಿರುವುದಿಲ್ಲ.
5. ಸ್ಕೋರ್ ಅನುಕ್ರಮ (ಔಟ್‌ಡಿಗ್ರಿಗಳ ಸೆಟ್). $T$ ಇದೆ $\{0,1,2,\ldots ,n-1\}$ .
6. $T$ ನಿಖರವಾಗಿ ಒಂದು ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಮಾರ್ಗವನ್ನು ಹೊಂದಿದೆ.

ರಾಮ್ಸೆ ಸಿದ್ಧಾಂತ

ಟ್ರಾನ್ಸಿಟಿವ್ ಟೂರ್ನಮೆಂಟ್‌ಗಳು ರಾಮ್‌ಸೇ ಸಿದ್ಧಾಂತದಲ್ಲಿ ಒಂದು ಪಾತ್ರವನ್ನು ವಹಿಸುತ್ತವೆ. ಇದು ಡೈರೆಕ್ಟೆಡ್ ಗ್ರಾಫ್‌ಗಳಲ್ಲಿನ ಗುಂಪುಗಳಿಗೆ ಹೋಲುತ್ತದೆ. ನಿರ್ದಿಷ್ಟವಾಗಿ, ಪ್ರತಿ ಟೂರ್ನಮೆಟ್ ನಲ್ಲಿ $n$ ವರ್ಟಿಸಿಸ್ ಗಳು ಒಂದು ಟ್ರಾನ್ಸಿಟಿವ್ ಸಬ್‌ಟೂರ್ನಮೆಂಟ್ ಅನ್ನು ಒಳಗೊಂಡಿದೆ $1+\lfloor \log _{2}n\rfloor$ ವರ್ಟಿಸಿಸ್ ಗಳು. ಪುರಾವೆ ಸರಳವಾಗಿದೆ: ಯಾವುದಾದರೂ ಒಂದು ವರ್ಟೆಕ್ಸ್ ಅನ್ನು ಆಯ್ಕೆಮಾಡಿ $v$ ಈ ಉಪ ಟೂರ್ನಮೆಂಟ್ ನ ಭಾಗವಾಗಿರಲು ಮತ್ತು ಉಪ ಟೂರ್ನಮೆಂಟ್ ನ ಉಳಿದ ಭಾಗವನ್ನು ಒಳಬರುವ ನೆರೆಹೊರೆಯವರ ಗುಂಪಿನಲ್ಲಿ ಪುನರಾವರ್ತಿತವಾಗಿ ರೂಪಿಸಲು $v$ ಅಥವಾ ಹೊರಹೋಗುವ ನೆರೆಹೊರೆಯವರ ಸೆಟ್ $v$, ಯಾವುದು ದೊಡ್ಡದು. ಉದಾಹರಣೆಗೆ, ಏಳು ವರ್ಟಿಸಿಸ್ ಗಳ ಮೇಲಿನ ಪ್ರತಿ ಟೂರ್ನಮೆಂಟ್ ನ ಮೂರು-ವರ್ಟಿಸಿಸ್ ಗಳ ಟ್ರಾನ್ಸಿಟಿವ್ ಸಬ್‌ಟೂರ್ನಮೆಂಟ್ ಅನ್ನು ಹೊಂದಿರುತ್ತದೆ; ಏಳು ವರ್ಟಿಸಿಸ್ ಗಳ ಮೇಲಿನ ಪೇಲಿ ಟೂರ್ನಮೆಂಟ್ - ಇದು ಅತ್ಯಂತ ಹೆಚ್ಚು ಖಾತರಿಪಡಿಸಬಹುದು ಎಂದು ತೋರಿಸುತ್ತದೆ ( ಎರ್ಡೋಸ್ ಮತ್ತು ಮೋಸೆರ್ ೧೯೬೪). ಆದಾಗ್ಯೂ, Reid & Parker (1970) ಕೆಲವು ದೊಡ್ಡ ಮೌಲ್ಯಗಳಿಗೆ ಈ ಮಿತಿಯು ಬಿಗಿಯಾಗಿಲ್ಲ ಎಂದು ತೋರಿಸಿದೆ $n$ .