2025-11-22T11:22:16.125593

Stability in Bondy's theorem on paths and cycles

Ning, Yuan
In this paper, we study the stability result of a well-known theorem of Bondy. We prove that for any 2-connected non-hamiltonian graph, if every vertex except for at most one vertex has degree at least $k$, then it contains a cycle of length at least $2k+2$ except for some special families of graphs. Our results imply several previous classical theorems including a deep and old result by Voss. We point out our result on stability in Bondy's theorem can directly imply a positive solution (in a slight stronger form) to the following problem: Is there a polynomial time algorithm to decide whether a 2-connected graph $G$ on $n$ vertices has a cycle of length at least $\min\{2δ(G)+2,n\}$. This problem originally motivates the recent study on algorithmic aspects of Dirac's theorem by Fomin, Golovach, Sagunov and Simonov, although a stronger problem was solved by them by completely different methods. Our theorem can also help us to determine all extremal graphs for wheels on odd number of vertices. We also discuss the relationship between our results and some previous problems and theorems in spectral graph theory and generalized TurÃƒÂĄn problem.
academic

āĻŦāĻ¨ā§āĻĄāĻŋ āωāĻĒāĻĒāĻžāĻĻā§āϝ⧇ āĻĒāĻĨ āĻāĻŦāĻ‚ āϚāĻ•ā§āϰ⧇āϰ āĻ¸ā§āĻĨāĻŋāϤāĻŋāĻļā§€āϞāϤāĻž

āĻŽā§ŒāϞāĻŋāĻ• āϤāĻĨā§āϝ

  • āĻĒāĻ¤ā§āϰ āφāχāĻĄāĻŋ: 2207.13650
  • āĻļāĻŋāϰ⧋āύāĻžāĻŽ: āĻŦāĻ¨ā§āĻĄāĻŋ āωāĻĒāĻĒāĻžāĻĻā§āϝ⧇ āĻĒāĻĨ āĻāĻŦāĻ‚ āϚāĻ•ā§āϰ⧇āϰ āĻ¸ā§āĻĨāĻŋāϤāĻŋāĻļā§€āϞāϤāĻž
  • āϞ⧇āĻ–āĻ•: āĻŦā§‹ āύāĻŋāĻ‚ (āύāĻžāύāĻ•āĻžāχ āĻŦāĻŋāĻļā§āĻŦāĻŦāĻŋāĻĻā§āϝāĻžāϞāϝāĻŧ), āϞāĻ‚-āϟ⧁ āχāωāϝāĻŧāĻžāύ (āĻĒā§‚āĻ°ā§āĻŦ āĻšā§€āύ āϏāĻžāϧāĻžāϰāĻŖ āĻŦāĻŋāĻļā§āĻŦāĻŦāĻŋāĻĻā§āϝāĻžāϞāϝāĻŧ)
  • āĻļā§āϰ⧇āĻŖā§€āĻŦāĻŋāĻ­āĻžāĻ—: math.CO (āϏāĻŽāĻ¨ā§āĻŦāϝāĻŧ āĻ—āĻŖāĻŋāϤ)
  • āĻĒā§āϰāĻ•āĻžāĻļāύāĻžāϰ āϏāĻŽāϝāĻŧ: ⧍ā§Ļ⧍⧍ āϏāĻžāϞ⧇āϰ āϜ⧁āϞāĻžāχāϝāĻŧ⧇ āϜāĻŽāĻž āĻĻ⧇āĻ“āϝāĻŧāĻž, ⧍ā§Ļā§¨ā§Š āϏāĻžāϞ⧇āϰ āĻĄāĻŋāϏ⧇āĻŽā§āĻŦāϰ⧇ āϏāĻ‚āĻļā§‹āϧāĻŋāϤ
  • āĻĒāĻ¤ā§āϰ āϞāĻŋāĻ™ā§āĻ•: https://arxiv.org/abs/2207.13650

āϏāĻžāϰāϏāĻ‚āĻ•ā§āώ⧇āĻĒ

āĻāχ āĻĒāĻ¤ā§āϰāϟāĻŋ āĻŦāĻŋāĻ–ā§āϝāĻžāϤ āĻŦāĻ¨ā§āĻĄāĻŋ āωāĻĒāĻĒāĻžāĻĻā§āϝ⧇āϰ āĻ¸ā§āĻĨāĻŋāϤāĻŋāĻļā§€āϞāϤāĻž āĻĢāϞāĻžāĻĢāϞ āĻ…āĻ§ā§āϝāϝāĻŧāύ āĻ•āϰ⧇āĨ¤ āϞ⧇āĻ–āĻ•āϰāĻž āĻĒā§āϰāĻŽāĻžāĻŖ āĻ•āϰ⧇āϛ⧇āύ āϝ⧇ āϝ⧇āϕ⧋āύ⧋ ⧍-āϏāĻ‚āϝ⧁āĻ•ā§āϤ āĻ…-āĻšā§āϝāĻžāĻŽāĻŋāϞāĻŸā§‹āύ⧀āϝāĻŧ āĻ—ā§āϰāĻžāĻĢ⧇āϰ āϜāĻ¨ā§āϝ, āϝāĻĻāĻŋ āϏāĻ°ā§āĻŦāĻžāϧāĻŋāĻ• āĻāĻ•āϟāĻŋ āĻļā§€āĻ°ā§āώāĻŦāĻŋāĻ¨ā§āĻĻ⧁ āĻ›āĻžāĻĄāĻŧāĻž āĻ…āĻ¨ā§āϝ āϏāĻ•āϞ āĻļā§€āĻ°ā§āώāĻŦāĻŋāĻ¨ā§āĻĻ⧁āϰ āĻĄāĻŋāĻ—ā§āϰāĻŋ āĻ•āĻŽāĻĒāĻ•ā§āώ⧇ k āĻšāϝāĻŧ, āϤāĻžāĻšāϞ⧇ āĻ—ā§āϰāĻžāĻĢāϟāĻŋ āĻ•āĻŽāĻĒāĻ•ā§āώ⧇ ⧍k+⧍ āĻĻ⧈āĻ°ā§āĻ˜ā§āϝ⧇āϰ āĻāĻ•āϟāĻŋ āϚāĻ•ā§āϰ āϧāĻžāϰāĻŖ āĻ•āϰ⧇, āĻ•āĻŋāϛ⧁ āĻŦāĻŋāĻļ⧇āώ āĻ—ā§āϰāĻžāĻĢ āĻĒāϰāĻŋāĻŦāĻžāϰ āĻ›āĻžāĻĄāĻŧāĻžāĨ¤ āĻāχ āĻĢāϞāĻžāĻĢāϞ āĻāĻ•āĻžāϧāĻŋāĻ• āĻ•ā§āϞāĻžāϏāĻŋāĻ•ā§āϝāĻžāϞ āωāĻĒāĻĒāĻžāĻĻā§āϝ āĻ…āĻ¨ā§āϤāĻ°ā§āϭ⧁āĻ•ā§āϤ āĻ•āϰ⧇, āϝāĻžāϰ āĻŽāĻ§ā§āϝ⧇ āϰāϝāĻŧ⧇āϛ⧇ āĻ­āĻ¸ā§-āĻāϰ āĻ—āĻ­ā§€āϰ āĻĢāϞāĻžāĻĢāϞāĨ¤ āϞ⧇āĻ–āĻ•āϰāĻž āύāĻŋāĻ°ā§āĻĻ⧇āĻļ āĻ•āϰ⧇āύ āϝ⧇ āĻŦāĻ¨ā§āĻĄāĻŋ āωāĻĒāĻĒāĻžāĻĻā§āϝ⧇āϰ āĻ¸ā§āĻĨāĻŋāϤāĻŋāĻļā§€āϞāϤāĻž āϏāĻŽā§āĻĒāĻ°ā§āĻ•āĻŋāϤ āϤāĻžāĻĻ⧇āϰ āĻĢāϞāĻžāĻĢāϞ āĻāĻ•āϟāĻŋ āϏāĻŽāĻ¸ā§āϝāĻžāϰ āχāϤāĻŋāĻŦāĻžāϚāĻ• āϏāĻŽāĻžāϧāĻžāύ āϏāϰāĻžāϏāϰāĻŋ āĻĒā§āϰāĻĻāĻžāύ āĻ•āϰ⧇: n āĻļā§€āĻ°ā§āώāĻŦāĻŋāĻ¨ā§āĻĻ⧁āϰ ⧍-āϏāĻ‚āϝ⧁āĻ•ā§āϤ āĻ—ā§āϰāĻžāĻĢ G-āϤ⧇ āĻ•āĻŽāĻĒāĻ•ā§āώ⧇ min{2δ(G)+2,n} āĻĻ⧈āĻ°ā§āĻ˜ā§āϝ⧇āϰ āϚāĻ•ā§āϰ āϰāϝāĻŧ⧇āϛ⧇ āĻ•āĻŋāύāĻž āϤāĻž āύāĻŋāĻ°ā§āϧāĻžāϰāĻŖ āĻ•āϰāĻžāϰ āϜāĻ¨ā§āϝ āĻŦāĻšā§āĻĒāĻĻā§€ āϏāĻŽāϝāĻŧ⧇āϰ āĻ…ā§āϝāĻžāϞāĻ—āϰāĻŋāĻĻāĻŽ āĻŦāĻŋāĻĻā§āϝāĻŽāĻžāύ āĻ•āĻŋāύāĻžāĨ¤

āĻ—āĻŦ⧇āώāĻŖāĻžāϰ āĻĒāϟāĻ­ā§‚āĻŽāĻŋ āĻāĻŦāĻ‚ āĻĒā§āϰ⧇āϰāĻŖāĻž

  1. āĻŽā§‚āϞ āϏāĻŽāĻ¸ā§āϝāĻž: āĻāχ āĻĒāĻ¤ā§āϰāϟāĻŋ āĻ—ā§āϰāĻžāĻĢ⧇āϰ āϚāĻ•ā§āϰ āĻĻ⧈āĻ°ā§āĻ˜ā§āϝ āĻāĻŦāĻ‚ āĻ¨ā§āϝ⧂āύāϤāĻŽ āĻĄāĻŋāĻ—ā§āϰāĻŋāϰ āĻŽāĻ§ā§āϝ⧇ āϏāĻŽā§āĻĒāĻ°ā§āĻ• āĻ…āĻ§ā§āϝāϝāĻŧāύ āĻ•āϰ⧇, āĻŦāĻŋāĻļ⧇āώāϤ "āĻĒā§āϰāĻžāϝāĻŧ āύāĻŋāϝāĻŧāĻŽāĻŋāϤ" āĻ—ā§āϰāĻžāĻĢ⧇ (āĻāĻ•āϟāĻŋ āĻļā§€āĻ°ā§āώāĻŦāĻŋāĻ¨ā§āĻĻ⧁ āĻ›āĻžāĻĄāĻŧāĻž āϏāĻ•āϞ āĻļā§€āĻ°ā§āώāĻŦāĻŋāĻ¨ā§āĻĻ⧁āϰ āĻĄāĻŋāĻ—ā§āϰāĻŋ āĻāĻ•āχ) āĻĻā§€āĻ°ā§āϘ āϚāĻ•ā§āϰ⧇āϰ āĻ…āĻ¸ā§āϤāĻŋāĻ¤ā§āĻŦ āϏāĻŽāĻ¸ā§āϝāĻžāϝāĻŧāĨ¤
  2. āϗ⧁āϰ⧁āĻ¤ā§āĻŦ:
    • āĻāχ āϏāĻŽāĻ¸ā§āϝāĻžāϟāĻŋ āϚāϰāĻŽ āĻ—ā§āϰāĻžāĻĢ āϤāĻ¤ā§āĻ¤ā§āĻŦ⧇āϰ āĻŽā§‚āϞ āĻŦāĻŋāώāϝāĻŧāĻŦāĻ¸ā§āϤ⧁, āĻšā§āϝāĻžāĻŽāĻŋāϞāĻŸā§‹āύ⧀āϝāĻŧ āϚāĻ•ā§āϰ āϤāĻ¤ā§āĻ¤ā§āĻŦ⧇āϰ āϏāĻžāĻĨ⧇ āϘāύāĻŋāĻˇā§āĻ āĻ­āĻžāĻŦ⧇ āϏāĻŽā§āĻĒāĻ°ā§āĻ•āĻŋāϤ
    • āĻŦāĻ°ā§āĻŖāĻžāϞ⧀ āĻ—ā§āϰāĻžāĻĢ āϤāĻ¤ā§āĻ¤ā§āĻŦ āĻāĻŦāĻ‚ āϏāĻžāϧāĻžāϰāĻŖā§€āĻ•ā§ƒāϤ āϟ⧁āϰāĻžāύ āϏāĻŽāĻ¸ā§āϝāĻžāϝāĻŧ āϗ⧁āϰ⧁āĻ¤ā§āĻŦāĻĒā§‚āĻ°ā§āĻŖ āĻĒā§āϰāϝāĻŧā§‹āĻ— āϰāϝāĻŧ⧇āϛ⧇
    • āĻ…ā§āϝāĻžāϞāĻ—āϰāĻŋāĻĻāĻŽāĻŋāĻ• āĻ—ā§āϰāĻžāĻĢ āϤāĻ¤ā§āĻ¤ā§āĻŦ⧇āϰ āϜāĻ¨ā§āϝ āϤāĻžāĻ¤ā§āĻ¤ā§āĻŦāĻŋāĻ• āĻ­āĻŋāĻ¤ā§āϤāĻŋ āĻĒā§āϰāĻĻāĻžāύ āĻ•āϰ⧇
  3. āĻŦāĻŋāĻĻā§āϝāĻŽāĻžāύ āĻĒāĻĻā§āϧāϤāĻŋāϰ āϏ⧀āĻŽāĻžāĻŦāĻĻā§āϧāϤāĻž:
    • āĻĄāĻŋāϰāĻžāĻ• āωāĻĒāĻĒāĻžāĻĻā§āϝ āϏāĻ•āϞ āĻļā§€āĻ°ā§āώāĻŦāĻŋāĻ¨ā§āĻĻ⧁āϰ āĻĄāĻŋāĻ—ā§āϰāĻŋ āϝāĻĨ⧇āĻˇā§āϟ āĻŦāĻĄāĻŧ āĻšāĻ“āϝāĻŧāĻžāϰ āĻĻāĻžāĻŦāĻŋ āĻ•āϰ⧇
    • āĻŦāĻ¨ā§āĻĄāĻŋ āωāĻĒāĻĒāĻžāĻĻā§āϝ āĻļāĻ°ā§āϤ āĻļāĻŋāĻĨāĻŋāϞ āĻ•āϰāϞ⧇āĻ“, āĻ¸ā§āĻĨāĻŋāϤāĻŋāĻļā§€āϞāϤāĻž āĻŦāĻŋāĻļā§āϞ⧇āώāϪ⧇āϰ āĻ…āĻ­āĻžāĻŦ āϰāϝāĻŧ⧇āϛ⧇
    • āϚāϰāĻŽ āĻ—ā§āϰāĻžāĻĢ āĻ•āĻžāĻ āĻžāĻŽā§‹āϰ āϏāĻŽā§āĻĒā§‚āĻ°ā§āĻŖ āĻŦāĻ°ā§āĻŖāύāĻžāϰ āĻ…āĻ­āĻžāĻŦ āϰāϝāĻŧ⧇āϛ⧇
  4. āĻ—āĻŦ⧇āώāĻŖāĻžāϰ āĻĒā§āϰ⧇āϰāĻŖāĻž:
    • āϚāϰāĻŽ āĻ—ā§āϰāĻžāĻĢ āϤāĻ¤ā§āĻ¤ā§āĻŦ⧇ āĻ¸ā§āĻĨāĻŋāϤāĻŋāĻļā§€āϞāϤāĻž āĻĢāϞāĻžāĻĢāϞ āĻĻā§āĻŦāĻžāϰāĻž āĻ…āύ⧁āĻĒā§āϰāĻžāĻŖāĻŋāϤ
    • āĻĢā§‹āĻŽāĻŋāύ āĻāĻŦāĻ‚ āĻ…āĻ¨ā§āϝāĻĻ⧇āϰ āĻĻā§āĻŦāĻžāϰāĻž āωāĻ¤ā§āĻĨāĻžāĻĒāĻŋāϤ āĻ…ā§āϝāĻžāϞāĻ—āϰāĻŋāĻĻāĻŽāĻŋāĻ• āϏāĻŽāĻ¸ā§āϝāĻž āϏāĻŽāĻžāϧāĻžāύ āĻ•āϰāĻž
    • āĻŦāĻŋāĻœā§‹āĻĄāĻŧ āϚāĻžāĻ•āĻž āĻ—ā§āϰāĻžāĻĢ⧇āϰ āϚāϰāĻŽ āĻ—ā§āϰāĻžāĻĢ āĻ•āĻžāĻ āĻžāĻŽā§‹ āύāĻŋāĻ°ā§āϧāĻžāϰāĻŖ āĻ•āϰāĻž

āĻŽā§‚āϞ āĻ…āĻŦāĻĻāĻžāύ

  1. āĻĒā§āϰāϧāĻžāύ āωāĻĒāĻĒāĻžāĻĻā§āϝ: āĻŦāĻ¨ā§āĻĄāĻŋ āωāĻĒāĻĒāĻžāĻĻā§āϝ⧇āϰ āĻ¸ā§āĻĨāĻŋāϤāĻŋāĻļā§€āϞāϤāĻž āϏāĻ‚āĻ¸ā§āĻ•āϰāĻŖ āĻĒā§āϰāĻŽāĻžāĻŖ āĻ•āϰāĻž (āωāĻĒāĻĒāĻžāĻĻā§āϝ ā§§.ā§Ŧ), āĻĒā§āϰāĻĻāĻ¤ā§āϤ āĻĄāĻŋāĻ—ā§āϰāĻŋ āĻļāĻ°ā§āϤ⧇ āϚāĻ•ā§āϰ āĻĻ⧈āĻ°ā§āĻ˜ā§āϝ āϏ⧀āĻŽāĻžāĻŦāĻĻā§āϧ āϚāϰāĻŽ āĻ—ā§āϰāĻžāĻĢ āϏāĻŽā§āĻĒā§‚āĻ°ā§āĻŖāĻ­āĻžāĻŦ⧇ āĻŦāĻ°ā§āĻŖāύāĻž āĻ•āϰāĻž
  2. āĻ…ā§āϝāĻžāϞāĻ—āϰāĻŋāĻĻāĻŽāĻŋāĻ• āĻĒā§āϰāϝāĻŧā§‹āĻ—: ⧍-āϏāĻ‚āϝ⧁āĻ•ā§āϤ āĻ—ā§āϰāĻžāĻĢ⧇ āĻ•āĻŽāĻĒāĻ•ā§āώ⧇ min{2δ(G)+2,n} āĻĻ⧈āĻ°ā§āĻ˜ā§āϝ⧇āϰ āϚāĻ•ā§āϰ āϰāϝāĻŧ⧇āϛ⧇ āĻ•āĻŋāύāĻž āϤāĻž āύāĻŋāĻ°ā§āϧāĻžāϰāϪ⧇āϰ āϜāĻ¨ā§āϝ āĻŦāĻšā§āĻĒāĻĻā§€ āϏāĻŽāϝāĻŧ⧇āϰ āĻ…ā§āϝāĻžāϞāĻ—āϰāĻŋāĻĻāĻŽ āĻĒā§āϰāĻĻāĻžāύ āĻ•āϰāĻž
  3. āϤāĻžāĻ¤ā§āĻ¤ā§āĻŦāĻŋāĻ• āĻāϕ⧀āĻ•āϰāĻŖ: āĻāĻ•āĻžāϧāĻŋāĻ• āĻ•ā§āϞāĻžāϏāĻŋāĻ•ā§āϝāĻžāϞ āĻĢāϞāĻžāĻĢāϞ (āφāϞāĻŋ-āĻ¸ā§āĻŸā§‡āϟāύ āωāĻĒāĻĒāĻžāĻĻā§āϝ, āύāĻŋāĻ•āĻŋāĻĢā§‹āϰāĻ­-āχāωāϝāĻŧāĻžāύ āωāĻĒāĻĒāĻžāĻĻā§āϝ āχāĻ¤ā§āϝāĻžāĻĻāĻŋ) āĻāĻ•āϟāĻŋ āĻ•āĻžāĻ āĻžāĻŽā§‹āϰ āĻ…āϧ⧀āύ⧇ āĻāϕ⧀āĻ­ā§‚āϤ āĻ•āϰāĻž
  4. āϚāϰāĻŽ āĻ—ā§āϰāĻžāĻĢ āĻŦāĻ°ā§āĻŖāύāĻž: āĻŦāĻŋāĻœā§‹āĻĄāĻŧ āϚāĻžāĻ•āĻž āĻ—ā§āϰāĻžāĻĢ W₂ₖ₊₃ āĻāϰ āϚāϰāĻŽ āĻ—ā§āϰāĻžāĻĢ āĻ•āĻžāĻ āĻžāĻŽā§‹ āϏāĻŽā§āĻĒā§‚āĻ°ā§āĻŖāĻ­āĻžāĻŦ⧇ āύāĻŋāĻ°ā§āϧāĻžāϰāĻŖ āĻ•āϰāĻž
  5. āĻĒāĻĻā§āϧāϤāĻŋāĻ—āϤ āωāĻĻā§āĻ­āĻžāĻŦāύ: "āĻĒāĻĨ āĻĻā§āϰāĻžāĻ•ā§āώāĻžāϞāϤāĻž" āĻ•ā§ŒāĻļāϞ āĻŦā§āϝāĻŦāĻšāĻžāϰ āĻ•āϰāĻž, āϐāϤāĻŋāĻšā§āϝāĻŦāĻžāĻšā§€ āϚāϰāĻŽ āĻ—ā§āϰāĻžāĻĢ āϤāĻ¤ā§āĻ¤ā§āĻŦ āĻĒāĻĻā§āϧāϤāĻŋ āĻĨ⧇āϕ⧇ āĻ­āĻŋāĻ¨ā§āύ

āĻĒāĻĻā§āϧāϤāĻŋāϰ āĻŦāĻŋāĻ¸ā§āϤāĻžāϰāĻŋāϤ āĻŦā§āϝāĻžāĻ–ā§āϝāĻž

āĻ•āĻžāĻœā§‡āϰ āϏāĻ‚āĻœā§āĻžāĻž

āχāύāĻĒ⧁āϟ: ⧍-āϏāĻ‚āϝ⧁āĻ•ā§āϤ āĻ…-āĻšā§āϝāĻžāĻŽāĻŋāϞāĻŸā§‹āύ⧀āϝāĻŧ n-āĻļā§€āĻ°ā§āώāĻŦāĻŋāĻ¨ā§āĻĻ⧁ āĻ—ā§āϰāĻžāĻĢ G, āϝ⧇āĻ–āĻžāύ⧇ āϏāĻ°ā§āĻŦāĻžāϧāĻŋāĻ• āĻāĻ•āϟāĻŋ āĻļā§€āĻ°ā§āώāĻŦāĻŋāĻ¨ā§āĻĻ⧁ āĻ›āĻžāĻĄāĻŧāĻž āĻ…āĻ¨ā§āϝ āϏāĻ•āϞ āĻļā§€āĻ°ā§āώāĻŦāĻŋāĻ¨ā§āĻĻ⧁āϰ āĻĄāĻŋāĻ—ā§āϰāĻŋ āĻ•āĻŽāĻĒāĻ•ā§āώ⧇ kâ‰Ĩ2 āφāωāϟāĻĒ⧁āϟ: G-āϤ⧇ āĻ•āĻŽāĻĒāĻ•ā§āώ⧇ ⧍k+āĨ¨ āĻĻ⧈āĻ°ā§āĻ˜ā§āϝ⧇āϰ āϚāĻ•ā§āϰ āϰāϝāĻŧ⧇āϛ⧇ āĻ•āĻŋāύāĻž āϤāĻž āύāĻŋāĻ°ā§āϧāĻžāϰāĻŖ āĻ•āϰāĻž, āϝāĻĻāĻŋ āύāĻž āĻĨāĻžāϕ⧇ āϤāĻžāĻšāϞ⧇ G-āĻāϰ āĻ•āĻžāĻ āĻžāĻŽā§‹ āĻŦāĻ°ā§āĻŖāύāĻž āĻ•āϰāĻž āϏ⧀āĻŽāĻžāĻŦāĻĻā§āϧāϤāĻž: āĻ—ā§āϰāĻžāĻĢ⧇āϰ āĻĒāϰāĻŋāϧāĻŋ c(G)≤āĨ¨k+āĨ§

āĻŽā§‚āϞ āĻĒā§āϰāϝ⧁āĻ•ā§āϤāĻŋāĻ—āϤ āĻĒāĻĻā§āϧāϤāĻŋ

ā§§. āĻĒāĻĨ āĻĻā§āϰāĻžāĻ•ā§āώāĻžāϞāϤāĻž āĻ•ā§ŒāĻļāϞ

  • āϏāĻ°ā§āĻŦāĻžāϧāĻŋāĻ• āĻĒāĻĨ P = x₁x₂...xₘ āύāĻŋāĻ°ā§āĻŦāĻžāϚāύ āĻ•āϰāĻž, āϝāĻžāϤ⧇ āĻĄāĻŋāĻ—ā§āϰāĻŋ k-āĻāϰ āĻšā§‡āϝāĻŧ⧇ āĻ•āĻŽ āĻļā§€āĻ°ā§āώāĻŦāĻŋāĻ¨ā§āĻĻ⧁āϰ āϏāĻ‚āĻ–ā§āϝāĻž āϏāĻ°ā§āĻŦāύāĻŋāĻŽā§āύ āĻšāϝāĻŧ
  • āĻ—ā§āϰāĻžāĻĢ⧇āϰ āĨ¨-āϏāĻ‚āϝ⧋āĻ—āϝ⧋āĻ—ā§āϝāϤāĻž āĻŦā§āϝāĻŦāĻšāĻžāϰ āĻ•āϰ⧇ āĻĒāĻĨ⧇āϰ āĻŽāĻ§ā§āϝ⧇ āϏāĻ‚āϝ⧋āĻ— āϤ⧈āϰāĻŋ āĻ•āϰāĻž
  • āĻĒā§āϰāϤāĻŋāĻŦ⧇āĻļā§€ āĻŦāĻŋāĻļā§āϞ⧇āώāϪ⧇āϰ āĻŽāĻžāĻ§ā§āϝāĻŽā§‡ āĻ—ā§āϰāĻžāĻĢ⧇āϰ āĻ•āĻžāĻ āĻžāĻŽā§‹ āύāĻŋāĻ°ā§āϧāĻžāϰāĻŖ āĻ•āϰāĻž

āĨ¨. āϕ⧇āϏ āĻŦāĻŋāĻļā§āϞ⧇āώāĻŖ āĻ•āĻžāĻ āĻžāĻŽā§‹

āĻĒāĻ¤ā§āϰāϟāĻŋ āĻĒā§āϰāĻŽāĻžāĻŖāϕ⧇ āĻĻ⧁āϟāĻŋ āĻĒā§āϰāϧāĻžāύ āĻ•ā§āώ⧇āĻ¤ā§āϰ⧇ āĻŦāĻŋāĻ­āĻ•ā§āϤ āĻ•āϰ⧇:

āϕ⧇āϏ āĨ§: āύāĻŋāĻ°ā§āĻĻāĻŋāĻˇā§āϟ āĻļāĻ°ā§āϤ āĻĒā§‚āϰāĻŖāĻ•āĻžāϰ⧀ āĻļā§€āĻ°ā§āώāĻŦāĻŋāĻ¨ā§āĻĻ⧁ āĻœā§‹āĻĄāĻŧāĻž (i,j) āĻŦāĻŋāĻĻā§āϝāĻŽāĻžāύ

  • āωāĻĒāϕ⧇āϏ āĨ§.āĨ§: āĻĒā§āϰāϤāĻŋāϟāĻŋ āϏāĻ°ā§āĻŦāĻžāϧāĻŋāĻ• āĻĒāĻĨ⧇ āϏāĻ°ā§āĻŦāĻžāϧāĻŋāĻ• āĻāĻ• āĻœā§‹āĻĄāĻŧāĻž āĻāχ āϧāϰāύ⧇āϰ āĻļā§€āĻ°ā§āώāĻŦāĻŋāĻ¨ā§āĻĻ⧁ āĻœā§‹āĻĄāĻŧāĻž āϰāϝāĻŧ⧇āϛ⧇
  • āωāĻĒāϕ⧇āϏ āĨ§.āĨ¨: āĻ•āĻŽāĻĒāĻ•ā§āώ⧇ āĻĻ⧁āϟāĻŋ āĻāχ āϧāϰāύ⧇āϰ āĻļā§€āĻ°ā§āώāĻŦāĻŋāĻ¨ā§āĻĻ⧁ āĻœā§‹āĻĄāĻŧāĻž āĻŦāĻŋāĻĻā§āϝāĻŽāĻžāύ

āϕ⧇āϏ āĨ¨: āϕ⧇āϏ āĨ§ āϘāĻŸā§‡ āύāĻž, āĻ•āĻŋāĻ¨ā§āϤ⧁ x₁ āĻāĻŦāĻ‚ xₘ āωāĻ­āϝāĻŧ⧇āϰ āĻĒā§āϰāϤāĻŋāĻŦ⧇āĻļā§€āϤ⧇ āĻāĻ•āϝ⧋āϗ⧇ āĻ…āĻ¨ā§āϤāĻ°ā§āϭ⧁āĻ•ā§āϤ āĻāĻ•āϟāĻŋ āĻļā§€āĻ°ā§āώāĻŦāĻŋāĻ¨ā§āĻĻ⧁ āĻŦāĻŋāĻĻā§āϝāĻŽāĻžāύ

āĨŠ. āĻŽā§‚āϞ āϞ⧇āĻŽā§āĻŽāĻž

āϞ⧇āĻŽā§āĻŽāĻž āĨ¨.āĨŠ: āĨ¨-āϏāĻ‚āϝ⧁āĻ•ā§āϤ āĻ—ā§āϰāĻžāĻĢ G āĻāĻŦāĻ‚ āĻļā§€āĻ°ā§āώāĻŦāĻŋāĻ¨ā§āĻĻ⧁ u,v-āĻāϰ āϜāĻ¨ā§āϝ, āϝāĻĻāĻŋ āĻĻā§€āĻ°ā§āϘāϤāĻŽ (u,v)-āĻĒāĻĨ āϏāĻ°ā§āĻŦāĻžāϧāĻŋāĻ• k+āĨ§ āϟāĻŋ āĻļā§€āĻ°ā§āώāĻŦāĻŋāĻ¨ā§āĻĻ⧁ āϧāĻžāϰāĻŖ āĻ•āϰ⧇, āĻāĻŦāĻ‚ u,v āĻāĻŦāĻ‚ āϏāĻ°ā§āĻŦāĻžāϧāĻŋāĻ• āĻāĻ•āϟāĻŋ āĻ…āĻ¨ā§āϝāĻžāĻ¨ā§āϝ āĻļā§€āĻ°ā§āώāĻŦāĻŋāĻ¨ā§āĻĻ⧁ āĻ›āĻžāĻĄāĻŧāĻž āĻ…āĻ¨ā§āϝ āϏāĻ•āϞ āĻļā§€āĻ°ā§āώāĻŦāĻŋāĻ¨ā§āĻĻ⧁āϰ āĻĄāĻŋāĻ—ā§āϰāĻŋ āĻ•āĻŽāĻĒāĻ•ā§āώ⧇ k āĻšāϝāĻŧ, āϤāĻžāĻšāϞ⧇ G-{u,v} = ℓKₖ₋₁âˆĒK₁ āĻ…āĻĨāĻŦāĻž G-{u,v} = ℓKₖ₋₁āĨ¤

āĻĒā§āϰāϝ⧁āĻ•ā§āϤāĻŋāĻ—āϤ āωāĻĻā§āĻ­āĻžāĻŦāύ⧀ āĻŦāĻŋāĻ¨ā§āĻĻ⧁

āĨ§. āĻĄāĻŋāĻ—ā§āϰāĻŋ āĻļāĻ°ā§āϤ⧇āϰ āύāĻŋāĻ°ā§āϭ⧁āϞ āĻĒāϰāĻŋāϚāĻžāϞāύāĻž: "āϏāĻ°ā§āĻŦāĻžāϧāĻŋāĻ• āĻāĻ•āϟāĻŋ āĻŦā§āϝāϤāĻŋāĻ•ā§āϰāĻŽ āĻļā§€āĻ°ā§āώāĻŦāĻŋāĻ¨ā§āĻĻ⧁" āĻļāĻ°ā§āϤ⧇āϰ āϚāϤ⧁āϰ āĻĒāϰāĻŋāϚāĻžāϞāύāĻž, āϝāĻž āϐāϤāĻŋāĻšā§āϝāĻŦāĻžāĻšā§€ āĻ¨ā§āϝ⧂āύāϤāĻŽ āĻĄāĻŋāĻ—ā§āϰāĻŋ āĻļāĻ°ā§āϤ⧇āϰ āĻšā§‡āϝāĻŧ⧇ āφāϰāĻ“ āϏ⧂āĻ•ā§āĻˇā§āĻŽ

āĨ¨. āĻ•āĻžāĻ āĻžāĻŽā§‹ āĻŦāĻŋāϝāĻŧā§‹āϜāύ āĻĒāĻĻā§āϧāϤāĻŋ: āĻĒāĻĨ āύāĻŋāĻ°ā§āĻŦāĻžāϚāύ āĻāĻŦāĻ‚ āĻĒā§āϰāϤāĻŋāĻŦ⧇āĻļā§€ āĻŦāĻŋāĻļā§āϞ⧇āώāϪ⧇āϰ āĻŽāĻžāĻ§ā§āϝāĻŽā§‡ āϜāϟāĻŋāϞ āĻ—ā§āϰāĻžāĻĢ āĻ•āĻžāĻ āĻžāĻŽā§‹āϕ⧇ āĻĒāϰāĻŋāϚāĻžāϞāύāĻžāϝ⧋āĻ—ā§āϝ āωāĻĒāĻžāĻĻāĻžāύ⧇ āĻŦāĻŋāϝāĻŧā§‹āϜāĻŋāϤ āĻ•āϰāĻž

āĨŠ. āϚāϰāĻŽ āĻ—ā§āϰāĻžāĻĢ⧇āϰ āϏāĻŽā§āĻĒā§‚āĻ°ā§āĻŖ āĻļā§āϰ⧇āĻŖā§€āĻŦāĻŋāĻ­āĻžāĻ—: āĻļ⧁āϧ⧁āĻŽāĻžāĻ¤ā§āϰ āϚāĻ•ā§āϰ āĻĻ⧈āĻ°ā§āĻ˜ā§āϝ⧇āϰ āύāĻŋāĻŽā§āύ āϏ⧀āĻŽāĻž āĻĒā§āϰāĻŽāĻžāĻŖ āĻ•āϰāĻž āύāϝāĻŧ, āĻŦāϰāĻ‚ āύāĻŋāĻŽā§āύ āϏ⧀āĻŽāĻž āĻ…āĻ°ā§āϜāύāĻ•āĻžāϰ⧀ āϚāϰāĻŽ āĻ—ā§āϰāĻžāĻĢ āϏāĻŽā§āĻĒā§‚āĻ°ā§āĻŖāĻ­āĻžāĻŦ⧇ āĻŦāĻ°ā§āĻŖāύāĻž āĻ•āϰāĻž

āĻĒāϰ⧀āĻ•ā§āώāĻžāĻŽā§‚āϞāĻ• āϏ⧇āϟāφāĻĒ

āĻāχ āĻĒāĻ¤ā§āϰāϟāĻŋ āĻŦāĻŋāĻļ⧁āĻĻā§āϧ āϤāĻžāĻ¤ā§āĻ¤ā§āĻŦāĻŋāĻ• āĻ—āĻŖāĻŋāϤ āĻĒāĻ¤ā§āϰ, āϝāĻž āĻĒāϰ⧀āĻ•ā§āώāĻžāĻŽā§‚āϞāĻ• āϝāĻžāϚāĻžāχāĻ•āϰāĻŖ āϜāĻĄāĻŧāĻŋāϤ āύāϝāĻŧāĨ¤ āϏāĻŽāĻ¸ā§āϤ āĻĢāϞāĻžāĻĢāϞ āĻ•āĻ ā§‹āϰ āĻ—āĻžāĻŖāĻŋāϤāĻŋāĻ• āĻĒā§āϰāĻŽāĻžāϪ⧇āϰ āĻŽāĻžāĻ§ā§āϝāĻŽā§‡ āĻĒā§āϰāĻžāĻĒā§āϤāĨ¤

āϤāĻžāĻ¤ā§āĻ¤ā§āĻŦāĻŋāĻ• āϝāĻžāϚāĻžāχāĻ•āϰāĻŖ āĻĒāĻĻā§āϧāϤāĻŋ

  • āĻ—āĻ āύāĻŽā§‚āϞāĻ• āĻĒā§āϰāĻŽāĻžāĻŖ: āĻĒā§āϰāϤāĻŋāϟāĻŋ āϚāϰāĻŽ āĻ—ā§āϰāĻžāĻĢ āĻļā§āϰ⧇āĻŖā§€āϰ āϜāĻ¨ā§āϝ āϝāĻžāϚāĻžāχ āĻ•āϰāĻž āϝ⧇ āĻāϟāĻŋ āϏāĻ¤ā§āϝāĻŋāχ āĻļāĻ°ā§āϤ āĻĒā§‚āϰāĻŖ āĻ•āϰ⧇
  • āĻĒā§āϰāĻŽāĻžāĻŖ āĻĻā§āĻŦāĻ¨ā§āĻĻā§āĻŦ āĻĻā§āĻŦāĻžāϰāĻž: āĻ…āĻ¨ā§āϝ āϕ⧋āύ⧋ āĻ•āĻžāĻ āĻžāĻŽā§‹ āĻŦāĻŋāĻĻā§āϝāĻŽāĻžāύ āĻŦāϞ⧇ āĻ…āύ⧁āĻŽāĻžāύ āĻ•āϰāĻž āĻāĻŦāĻ‚ āĻŦāĻŋāϰ⧋āϧāĻŋāϤāĻž āωāĻĻā§āĻ­āĻŦ āĻ•āϰāĻž
  • āφāĻŦāĻ°ā§āϤāĻ• āĻŦāĻŋāĻļā§āϞ⧇āώāĻŖ: āĻŦāĻŋāĻ­āĻŋāĻ¨ā§āύ āĻĒā§āϝāĻžāϰāĻžāĻŽāĻŋāϟāĻžāϰ āĻŽāĻžāύ⧇āϰ āϜāĻ¨ā§āϝ āφāϞāĻžāĻĻāĻžāĻ­āĻžāĻŦ⧇ āĻĒāϰāĻŋāϚāĻžāϞāύāĻž āĻ•āϰāĻž

āĻĒā§āϰāϧāĻžāύ āĻĢāϞāĻžāĻĢāϞ

āωāĻĒāĻĒāĻžāĻĻā§āϝ āĨ§.āĨŦ (āĻĒā§āϰāϧāĻžāύ āĻĢāϞāĻžāĻĢāϞ)

G āϝāĻĻāĻŋ āĨ¨-āϏāĻ‚āϝ⧁āĻ•ā§āϤ āĻ…-āĻšā§āϝāĻžāĻŽāĻŋāϞāĻŸā§‹āύ⧀āϝāĻŧ n-āĻļā§€āĻ°ā§āώāĻŦāĻŋāĻ¨ā§āĻĻ⧁ āĻ—ā§āϰāĻžāĻĢ āĻšāϝāĻŧ āĻāĻŦāĻ‚ c(G)≤āĨ¨k+āĨ§ āĻšāϝāĻŧāĨ¤ āϝāĻĻāĻŋ āϏāĻ°ā§āĻŦāĻžāϧāĻŋāĻ• āĻāĻ•āϟāĻŋ āĻļā§€āĻ°ā§āώāĻŦāĻŋāĻ¨ā§āĻĻ⧁ āĻ›āĻžāĻĄāĻŧāĻž āĻ…āĻ¨ā§āϝ āϏāĻ•āϞ āĻļā§€āĻ°ā§āώāĻŦāĻŋāĻ¨ā§āĻĻ⧁āϰ āĻĄāĻŋāĻ—ā§āϰāĻŋ āĻ•āĻŽāĻĒāĻ•ā§āώ⧇ kâ‰ĨāĨ¨ āĻšāϝāĻŧ, āϤāĻžāĻšāϞ⧇ G āύāĻŋāĻŽā§āύāϞāĻŋāĻ–āĻŋāϤ āĻ—ā§āϰāĻžāĻĢāϗ⧁āϞāĻŋāϰ āĻāĻ•āϟāĻŋāϰ āωāĻĒāĻ—ā§āϰāĻžāĻĢ:

āĨ§. H-āĻĒā§āϰāĻ•āĻžāϰ āĻ—ā§āϰāĻžāĻĢ: H(āĨ¨k+āĨ§,āĨ¨k+āĨ§,k) āĻāĻŦāĻ‚ H(n,āĨ¨k+āĨ¨,k) (nâ‰ĨāĨ¨k+āĨ¨) āĨ¨. F-āĻĒā§āϰāĻ•āĻžāϰ āĻ—ā§āϰāĻžāĻĢ: F(s,t,k) (sâ‰ĨāĨ§,tâ‰ĨāĨ§) āĻāĻŦāĻ‚ F₁(t,k) (tâ‰ĨāĨ§)
āĨŠ. āĻŦāĻŋāĻļ⧇āώ āϛ⧋āϟ āĻ—ā§āϰāĻžāĻĢ:

  • K₂+Mₜ (tâ‰ĨāĨŦ)
  • K₂+(SₛâˆĒMₜ) (s+tâ‰ĨāĨŦ, āϝāĻ–āύ k=āĨŠ)
  • K₃+Mₜ (tâ‰ĨāĨ­, āϝāĻ–āύ k=āĨĒ)

āĻ…āύ⧁āϏāĻŋāĻĻā§āϧāĻžāĻ¨ā§āϤ āĻāĻŦāĻ‚ āĻĒā§āϰāϝāĻŧā§‹āĻ—

āωāĻĒāĻĒāĻžāĻĻā§āϝ āĨŠ.āĨŠ (āĻĒāĻĨ āϏāĻ‚āĻ¸ā§āĻ•āϰāĻŖ)

āϏāĻ‚āϝ⧁āĻ•ā§āϤ āĻ—ā§āϰāĻžāĻĢ⧇āϰ āϜāĻ¨ā§āϝ, min{n,āĨ¨k+āĨŠ} āĻĻ⧈āĻ°ā§āĻ˜ā§āϝ⧇āϰ āĻĒāĻĨ āϧāĻžāϰāĻŖ āύāĻž āĻ•āϰāĻž āĻ—ā§āϰāĻžāĻĢ⧇āϰ āϏāĻŽā§āĻĒā§‚āĻ°ā§āĻŖ āĻŦāĻ°ā§āĻŖāύāĻž āĻĒā§āϰāĻĻāĻžāύ āĻ•āϰāĻžāĨ¤

āωāĻĒāĻĒāĻžāĻĻā§āϝ āĨŠ.āĨĢ (āϚāϰāĻŽ āĻ—ā§āϰāĻžāĻĢ āĻĒā§āϰāϝāĻŧā§‹āĻ—)

{Sₖ₊āĨ¨,PāĨ¨â‚–₊āĨ§}-āĻŽā§āĻ•ā§āϤ āĻ—ā§āϰāĻžāĻĢ⧇āϰ āϚāϰāĻŽ āĻ—ā§āϰāĻžāĻĢ āϏāĻ°ā§āĻŦāĻžāϧāĻŋāĻ• āĨ¨k āĻ•ā§āϰāĻŽ āϏāĻš āϏāĻ‚āϝ⧁āĻ•ā§āϤ āωāĻĒāĻžāĻĻāĻžāύ āύāĻŋāϝāĻŧ⧇ āĻ—āĻ āĻŋāϤ āĻĒā§āϰāĻŽāĻžāĻŖ āĻ•āϰāĻžāĨ¤

āĻ…ā§āϝāĻžāϞāĻ—āϰāĻŋāĻĻāĻŽ āĻĢāϞāĻžāĻĢāϞ

O(kn) āϏāĻŽāϝāĻŧ āϜāϟāĻŋāϞāϤāĻžāϰ āϏāĻžāĻĨ⧇ āĻ…ā§āϝāĻžāϞāĻ—āϰāĻŋāĻĻāĻŽ āĻĒā§āϰāĻĻāĻžāύ āĻ•āϰāĻž, āϝāĻž āĻ—ā§āϰāĻžāĻĢ⧇ ā¤•ā¤Žā¤Ē⤕āĨā¤ˇ āĨ¨k+āĨ¨ āĻĻ⧈āĻ°ā§āĻ˜ā§āϝ⧇āϰ āϚāĻ•āĨā¤° āϰāϝāĻŧ⧇āϛ⧇ āĻ•āĻŋāύāĻž āϤāĻž āύāĻŋāĻ°ā§āϧāĻžāϰāĻŖ āĻ•āϰ⧇āĨ¤

āϏāĻŽā§āĻĒāĻ°ā§āĻ•āĻŋāϤ āĻ•āĻžāϜ

āϐāϤāĻŋāĻšāĻžāϏāĻŋāĻ• āωāĻ¨ā§āύāϝāĻŧāύ āĻĒāĻĨ

āĨ§. āĻĄāĻŋāϰāĻžāĻ• āωāĻĒāĻĒāĻžāĻĻā§āϝ (āĨ§āĨ¯āĨĢāĨ¨): δ(G)â‰Ĩn/āĨ¨ ⟹ G-āϤ⧇ āĻšā§āϝāĻžāĻŽāĻŋāϞāĻŸā§‹āύ⧀āϝāĻŧ āϚāĻ•ā§āϰ āϰāϝāĻŧ⧇āϛ⧇ āĨ¨. āĻŦāĻ¨ā§āĻĄāĻŋ āωāĻĒāĻĒāĻžāĻĻā§āϝ (āĨ§āĨ¯āĨ­āĨ§): "āϏāĻ°ā§āĻŦāĻžāϧāĻŋāĻ• āĻāĻ•āϟāĻŋ āĻŦā§āϝāϤāĻŋāĻ•ā§āϰāĻŽ āĻļā§€āĻ°ā§āώāĻŦāĻŋāĻ¨ā§āĻĻ⧁"-āϤ⧇ āĻļāĻŋāĻĨāĻŋāϞ āĻ•āϰāĻž āĨŠ. āĻ­āĻ¸ā§ āωāĻĒāĻĒāĻžāĻĻā§āϝ (āĨ§āĨ¯āĨ¯āĨ§): āύāĻŋāĻŽā§āύ āϏ⧀āĻŽāĻž āωāĻ¨ā§āύāϤ āĻ•āϰāĻž āĻāĻŦāĻ‚ āϚāϰāĻŽ āĻ—ā§āϰāĻžāĻĢ āĻŦāĻ°ā§āĻŖāύāĻž āĻ•āϰāĻž āĨĒ. āĻāχ āĻĒāĻ¤ā§āϰ: āϏāĻŽā§āĻĒā§‚āĻ°ā§āĻŖ āĻ¸ā§āĻĨāĻŋāϤāĻŋāĻļā§€āϞāϤāĻž āĻŦāĻŋāĻļā§āϞ⧇āώāĻŖ

āϏāĻŽā§āĻĒāĻ°ā§āĻ•āĻŋāϤ āĻ•ā§āώ⧇āĻ¤ā§āϰ⧇āϰ āϏāĻ‚āϝ⧋āĻ—

  • āĻŦāĻ°ā§āĻŖāĻžāϞ⧀ āĻ—ā§āϰāĻžāĻĢ āϤāĻ¤ā§āĻ¤ā§āĻŦ: āύāĻŋāĻ•āĻŋāĻĢā§‹āϰāĻ­-āχāωāϝāĻŧāĻžāύ āĻāĻŦāĻ‚ āĻ…āĻ¨ā§āϝāĻĻ⧇āϰ āĻŦāĻ°ā§āĻŖāĻžāϞ⧀ āĻŦā§āϝāĻžāϏāĻžāĻ°ā§āϧ āĻ—āĻŦ⧇āώāĻŖāĻžāϰ āϏāĻžāĻĨ⧇ āϏāĻŽā§āĻĒāĻ°ā§āĻ•āĻŋāϤ
  • āϟ⧁āϰāĻžāύ āϤāĻ¤ā§āĻ¤ā§āĻŦ: āϏāĻžāϧāĻžāϰāĻŖā§€āĻ•ā§ƒāϤ āϟ⧁āϰāĻžāύ āϏāĻŽāĻ¸ā§āϝāĻžāϰ āϏāĻžāĻĨ⧇ āϏāĻ‚āϝ⧋āĻ—
  • āĻ…ā§āϝāĻžāϞāĻ—āϰāĻŋāĻĻāĻŽāĻŋāĻ• āĻ—ā§āϰāĻžāĻĢ āϤāĻ¤ā§āĻ¤ā§āĻŦ: āĻĢā§‹āĻŽāĻŋāύ āĻāĻŦāĻ‚ āĻ…āĻ¨ā§āϝāĻĻ⧇āϰ āĻ…ā§āϝāĻžāϞāĻ—āϰāĻŋāĻĻāĻŽ āĻ—āĻŦ⧇āώāĻŖāĻžāϰ āϜāĻ¨ā§āϝ āϤāĻžāĻ¤ā§āĻ¤ā§āĻŦāĻŋāĻ• āĻ­āĻŋāĻ¤ā§āϤāĻŋ āĻĒā§āϰāĻĻāĻžāύ āĻ•āϰāĻž

āωāĻĒāϏāĻ‚āĻšāĻžāϰ āĻāĻŦāĻ‚ āφāϞ⧋āϚāύāĻž

āĻĒā§āϰāϧāĻžāύ āωāĻĒāϏāĻ‚āĻšāĻžāϰ

āĨ§. āĻŦāĻ¨ā§āĻĄāĻŋ āωāĻĒāĻĒāĻžāĻĻā§āϝ⧇āϰ āĻ¸ā§āĻĨāĻŋāϤāĻŋāĻļā§€āϞāϤāĻž āϏāĻŽāĻ¸ā§āϝāĻž āϏāĻŽā§āĻĒā§‚āĻ°ā§āĻŖāĻ­āĻžāĻŦ⧇ āϏāĻŽāĻžāϧāĻžāύ āĻ•āϰāĻž, āϏāĻŽāĻ¸ā§āϤ āϚāϰāĻŽ āĻ—ā§āϰāĻžāĻĢ⧇āϰ āύāĻŋāĻ°ā§āϭ⧁āϞ āĻŦāĻ°ā§āĻŖāύāĻž āĻĒā§āϰāĻĻāĻžāύ āĻ•āϰāĻž āĨ¨. āĻāĻ•āĻžāϧāĻŋāĻ• āĻ•ā§āϞāĻžāϏāĻŋāĻ•ā§āϝāĻžāϞ āĻĢāϞāĻžāĻĢāϞ āĻāϕ⧀āĻ­ā§‚āϤ āĻ•āϰāĻž, āϤāĻ¤ā§āĻ¤ā§āĻŦ⧇āϰ āĻ…āĻ­ā§āϝāĻ¨ā§āϤāϰ⧀āĻŖ āϏāĻ‚āϝ⧋āĻ— āĻĒā§āϰāĻĻāĻ°ā§āĻļāύ āĻ•āϰāĻž āĨŠ. āϏāĻŽā§āĻĒāĻ°ā§āĻ•āĻŋāϤ āĻ…ā§āϝāĻžāϞāĻ—āϰāĻŋāĻĻāĻŽ āϏāĻŽāĻ¸ā§āϝāĻžāϰ āϜāĻ¨ā§āϝ āĻ•āĻžāĻ°ā§āϝāĻ•āϰ āϏāĻŽāĻžāϧāĻžāύ āĻĒā§āϰāĻĻāĻžāύ āĻ•āϰāĻž

āϏ⧀āĻŽāĻžāĻŦāĻĻā§āϧāϤāĻž

āĨ§. āĻĒā§āϝāĻžāϰāĻžāĻŽāĻŋāϟāĻžāϰ āϏ⧀āĻŽāĻžāĻŦāĻĻā§āϧāϤāĻž: kâ‰ĨāĨ¨ āĻĒā§āϰāϝāĻŧā§‹āϜāύ, āϛ⧋āϟ āĻĒā§āϝāĻžāϰāĻžāĻŽāĻŋāϟāĻžāϰ āĻ•ā§āώ⧇āĻ¤ā§āϰ⧇ āĻŦāĻŋāĻļ⧇āώ āĻĒāϰāĻŋāϚāĻžāϞāύāĻž āĻĒā§āϰāϝāĻŧā§‹āϜāύ āĨ¨. āĨ¨-āϏāĻ‚āϝ⧋āĻ—āϝ⧋āĻ—ā§āϝāϤāĻž āĻ…āύ⧁āĻŽāĻžāύ: āĻĒāĻĻā§āϧāϤāĻŋ āĻ—ā§āϰāĻžāĻĢ⧇āϰ āĨ¨-āϏāĻ‚āϝ⧋āĻ—āϝ⧋āĻ—ā§āϝāϤāĻžāϰ āωāĻĒāϰ āϗ⧁āϰ⧁āϤāϰāĻ­āĻžāĻŦ⧇ āύāĻŋāĻ°ā§āĻ­āϰ āĻ•āϰ⧇ āĨŠ. āĻ…-āĻ—āĻ āύāĻŽā§‚āϞāĻ•: āϝāĻĻāĻŋāĻ“ āĻ…ā§āϝāĻžāϞāĻ—āϰāĻŋāĻĻāĻŽ āĻĒā§āϰāĻĻāĻžāύ āĻ•āϰāĻž āĻšāϝāĻŧ⧇āϛ⧇, āĻĒā§āϰāϧāĻžāύ āĻĢāϞāĻžāĻĢāϞ āĻ…āĻ¸ā§āϤāĻŋāĻ¤ā§āĻŦ āωāĻĒāĻĒāĻžāĻĻā§āϝ

āĻ­āĻŦāĻŋāĻˇā§āϝāϤ āĻĻāĻŋāĻ•āύāĻŋāĻ°ā§āĻĻ⧇āĻļāύāĻž

āĨ§. āφāϰāĻ“ āϏāĻžāϧāĻžāϰāĻŖ āĻ—ā§āϰāĻžāĻĢ āĻļā§āϰ⧇āĻŖā§€āϤ⧇ āϏāĻŽā§āĻĒā§āϰāϏāĻžāϰāĻŖ: āĻ…-āĨ¨-āϏāĻ‚āϝ⧁āĻ•ā§āϤ āĻ—ā§āϰāĻžāĻĢ⧇āϰ āĻ•ā§āώ⧇āĻ¤ā§āϰ⧇ āĻ—āĻŦ⧇āώāĻŖāĻž āĻ•āϰāĻž āĨ¨. āĻĒā§āϝāĻžāϰāĻžāĻŽāĻŋāϟāĻžāϰ āĻ…āĻĒā§āϟāĻŋāĻŽāĻžāχāĻœā§‡āĻļāύ: āĻĄāĻŋāĻ—ā§āϰāĻŋ āĻļāĻ°ā§āϤ āĻŦāĻž āϚāĻ•ā§āϰ āĻĻ⧈āĻ°ā§āĻ˜ā§āϝ āύāĻŋāĻŽā§āύ āϏ⧀āĻŽāĻž āφāϰāĻ“ āωāĻ¨ā§āύāϤ āĻ•āϰāĻž āĨŠ. āĻ…ā§āϝāĻžāϞāĻ—āϰāĻŋāĻĻāĻŽ āωāĻ¨ā§āύāϤāĻŋ: āφāϰāĻ“ āĻĻāĻ•ā§āώ āύāĻŋāĻ°ā§āϧāĻžāϰāĻŖ āĻ…ā§āϝāĻžāϞāĻ—āϰāĻŋāĻĻāĻŽ āĻŦāĻŋāĻ•āĻžāĻļ āĻ•āϰāĻž āĨĒ. āĻĒā§āϰāϝāĻŧā§‹āĻ— āϏāĻŽā§āĻĒā§āϰāϏāĻžāϰāĻŖ: āĻ…āĻ¨ā§āϝāĻžāĻ¨ā§āϝ āĻ—ā§āϰāĻžāĻĢ āϤāĻ¤ā§āĻ¤ā§āĻŦ āϏāĻŽāĻ¸ā§āϝāĻžāϝāĻŧ āĻ¸ā§āĻĨāĻŋāϤāĻŋāĻļā§€āϞāϤāĻž āĻĒāĻĻā§āϧāϤāĻŋ āĻĒā§āϰāϝāĻŧā§‹āĻ— āĻ•āϰāĻž

āĻ—āĻ­ā§€āϰ āĻŽā§‚āĻ˛ā§āϝāĻžāϝāĻŧāύ

āϏ⧁āĻŦāĻŋāϧāĻž

āĨ§. āϤāĻžāĻ¤ā§āĻ¤ā§āĻŦāĻŋāĻ• āĻ—āĻ­ā§€āϰāϤāĻž: āĻāĻ•āϟāĻŋ āĻ•āĻ āĻŋāύ āϚāϰāĻŽ āĻ—ā§āϰāĻžāĻĢ āϤāĻ¤ā§āĻ¤ā§āĻŦ āϏāĻŽāĻ¸ā§āϝāĻž āϏāĻŽā§āĻĒā§‚āĻ°ā§āĻŖāĻ­āĻžāĻŦ⧇ āϏāĻŽāĻžāϧāĻžāύ āĻ•āϰāĻž, āĻĒā§āϰāϝ⧁āĻ•ā§āϤāĻŋāĻ—āϤ āĻĒā§āϰāϝāĻŧā§‹āϜāύ⧀āϝāĻŧāϤāĻž āĻ…āĻ¤ā§āϝāĻ¨ā§āϤ āωāĻšā§āϚ āĨ¨. āĻĒāĻĻā§āϧāϤāĻŋāĻ—āϤ āωāĻĻā§āĻ­āĻžāĻŦāύ: "āĻĒāĻĨ āĻĻā§āϰāĻžāĻ•ā§āώāĻžāϞāϤāĻž" āĻ•ā§ŒāĻļāϞ⧇āϰ āĻĒā§āϰāϝāĻŧā§‹āĻ— āύāϤ⧁āύ āĻĒā§āϰāĻŽāĻžāĻŖ āϚāĻŋāĻ¨ā§āϤāĻžāĻ­āĻžāĻŦāύāĻž āĻĒā§āϰāĻĻāĻ°ā§āĻļāύ āĻ•āϰ⧇ āĨŠ. āĻĢāϞāĻžāĻĢāϞ āϏāĻŽā§āĻĒā§‚āĻ°ā§āĻŖāϤāĻž: āĻļ⧁āϧ⧁āĻŽāĻžāĻ¤ā§āϰ āĻĒā§āϰāϧāĻžāύ āωāĻĒāĻĒāĻžāĻĻā§āϝ āĻĒā§āϰāĻŽāĻžāĻŖ āĻ•āϰāĻž āύāϝāĻŧ, āĻŦāϰāĻ‚ āϏāĻŽā§ƒāĻĻā§āϧ āĻ…āύ⧁āϏāĻŋāĻĻā§āϧāĻžāĻ¨ā§āϤ āĻāĻŦāĻ‚ āĻĒā§āϰāϝāĻŧā§‹āĻ— āĻĒā§āϰāĻĻāĻžāύ āĻ•āϰāĻž āĨĒ. āφāĻ¨ā§āϤāσāĻļ⧃āĻ™ā§āĻ–āϞāĻž āĻĒā§āϰāĻ­āĻžāĻŦ: āϚāϰāĻŽ āĻ—ā§āϰāĻžāĻĢ āϤāĻ¤ā§āĻ¤ā§āĻŦ, āĻŦāĻ°ā§āĻŖāĻžāϞ⧀ āĻ—ā§āϰāĻžāĻĢ āϤāĻ¤ā§āĻ¤ā§āĻŦ āĻāĻŦāĻ‚ āĻ…ā§āϝāĻžāϞāĻ—āϰāĻŋāĻĻāĻŽāĻŋāĻ• āĻ—ā§āϰāĻžāĻĢ āϤāĻ¤ā§āĻ¤ā§āĻŦ āϏāĻ‚āϝ⧋āĻ— āĻ•āϰāĻž

āĻ…āĻĒā§‚āĻ°ā§āĻŖāϤāĻž

āĨ§. āĻĒā§āϰāĻŽāĻžāĻŖ āϜāϟāĻŋāϞāϤāĻž: āϕ⧇āϏ āĻŦāĻŋāĻļā§āϞ⧇āώāĻŖ āĻ…āĻ¤ā§āϝāĻ¨ā§āϤ āϜāϟāĻŋāϞ, āϏāĻŽā§āĻ­āĻŦāϤ āφāϰāĻ“ āϏāĻ‚āĻ•ā§āώāĻŋāĻĒā§āϤ āĻĒā§āϰāĻŽāĻžāĻŖ āĻĒāĻĻā§āϧāϤāĻŋ āĻŦāĻŋāĻĻā§āϝāĻŽāĻžāύ āĨ¨. āĻĒāĻžāĻ āϝ⧋āĻ—ā§āϝāϤāĻž: āĻĒā§āϰāϝ⧁āĻ•ā§āϤāĻŋāĻ—āϤ āĻŦāĻŋāĻŦāϰāĻŖ āĻ…āύ⧇āĻ• āĻŦ⧇āĻļāĻŋ, āĻ…-āĻŦāĻŋāĻļ⧇āώāĻœā§āĻž āĻĒāĻžāĻ āĻ•āĻĻ⧇āϰ āϜāĻ¨ā§āϝ āϝāĻĨ⧇āĻˇā§āϟ āĻŦāĻ¨ā§āϧ⧁āĻ¤ā§āĻŦāĻĒā§‚āĻ°ā§āĻŖ āύāϝāĻŧ āĨŠ. āĻŦā§āϝāĻŦāĻšāĻžāϰāĻŋāĻ• āĻĒā§āϰāϝāĻŧā§‹āĻ—: āϝāĻĻāĻŋāĻ“ āĻ…ā§āϝāĻžāϞāĻ—āϰāĻŋāĻĻāĻŽ āĻĒā§āϰāϝāĻŧā§‹āĻ— āϰāϝāĻŧ⧇āϛ⧇, āĻŦā§āϝāĻŦāĻšāĻžāϰāĻŋāĻ• āĻŽā§‚āĻ˛ā§āϝ āϏ⧀āĻŽāĻŋāϤ

āĻĒā§āϰāĻ­āĻžāĻŦ

āĨ§. āϤāĻžāĻ¤ā§āĻ¤ā§āĻŦāĻŋāĻ• āĻ…āĻŦāĻĻāĻžāύ: āϚāϰāĻŽ āĻ—ā§āϰāĻžāĻĢ āϤāĻ¤ā§āĻ¤ā§āĻŦ⧇āϰ āϜāĻ¨ā§āϝ āϗ⧁āϰ⧁āĻ¤ā§āĻŦāĻĒā§‚āĻ°ā§āĻŖ āĻ¸ā§āĻĨāĻŋāϤāĻŋāĻļā§€āϞāϤāĻž āĻĢāϞāĻžāĻĢāϞ āĻĒā§āϰāĻĻāĻžāύ āĻ•āϰāĻž āĨ¨. āĻĒāĻĻā§āϧāϤāĻŋāĻ—āϤ āĻŽā§‚āĻ˛ā§āϝ: āĻĒā§āϰāĻŽāĻžāĻŖ āĻ•ā§ŒāĻļāϞ āĻ…āĻ¨ā§āϝāĻžāĻ¨ā§āϝ āĻ…āύ⧁āϰ⧂āĻĒ āϏāĻŽāĻ¸ā§āϝāĻžāϝāĻŧ āĻĒā§āϰāϝāĻŧā§‹āĻ— āĻ•āϰāĻž āϝ⧇āϤ⧇ āĻĒāĻžāϰ⧇ āĨŠ. āĻĒāϰāĻŦāĻ°ā§āϤ⧀ āĻ—āĻŦ⧇āώāĻŖāĻž: āχāϤāĻŋāĻŽāĻ§ā§āϝ⧇ āĻāĻ•āĻžāϧāĻŋāĻ• āĻĒāϰāĻŦāĻ°ā§āϤ⧀ āĻĒāĻ¤ā§āϰ āĻĻā§āĻŦāĻžāϰāĻž āωāĻĻā§āϧ⧃āϤ āĻāĻŦāĻ‚ āωāĻ¨ā§āύāϤ āĻ•āϰāĻž āĻšāϝāĻŧ⧇āϛ⧇

āĻĒā§āϰāϝ⧋āĻœā§āϝ āĻĒāϰāĻŋāĻ¸ā§āĻĨāĻŋāϤāĻŋ

āĨ§. āϤāĻžāĻ¤ā§āĻ¤ā§āĻŦāĻŋāĻ• āĻ—āĻŦ⧇āώāĻŖāĻž: āϚāϰāĻŽ āĻ—ā§āϰāĻžāĻĢ āϤāĻ¤ā§āĻ¤ā§āĻŦ, āĻ•āĻžāĻ āĻžāĻŽā§‹āĻ—āϤ āĻ—ā§āϰāĻžāĻĢ āϤāĻ¤ā§āĻ¤ā§āĻŦ⧇āϰ āĻ—āĻŦ⧇āώāĻŖāĻž āĨ¨. āĻ…ā§āϝāĻžāϞāĻ—āϰāĻŋāĻĻāĻŽ āĻĄāĻŋāϜāĻžāχāύ: āĻ—ā§āϰāĻžāĻĢ⧇ āĻĻā§€āĻ°ā§āϘ āϚāĻ•ā§āϰ āϏāύāĻžāĻ•ā§āϤāĻ•āϰāĻŖ āĻ…ā§āϝāĻžāϞāĻ—āϰāĻŋāĻĻāĻŽā§‡āϰ āϤāĻžāĻ¤ā§āĻ¤ā§āĻŦāĻŋāĻ• āĻ­āĻŋāĻ¤ā§āϤāĻŋ āĨŠ. āĻŦāĻ°ā§āĻŖāĻžāϞ⧀ āĻ—ā§āϰāĻžāĻĢ āϤāĻ¤ā§āĻ¤ā§āĻŦ: āĻŦāĻ°ā§āĻŖāĻžāϞ⧀ āĻĒāĻĻā§āϧāϤāĻŋāϰ āĻĒāϰāĻŋāĻĒā§‚āϰāĻ• āĻšāĻžāϤāĻŋāϝāĻŧāĻžāϰ āĻšāĻŋāϏāĻžāĻŦ⧇

āϤāĻĨā§āϝāϏ⧂āĻ¤ā§āϰ

āĻĒāĻ¤ā§āϰāϟāĻŋ ⧍āĨŽāϟāĻŋ āϗ⧁āϰ⧁āĻ¤ā§āĻŦāĻĒā§‚āĻ°ā§āĻŖ āϤāĻĨā§āϝāϏ⧂āĻ¤ā§āϰ āωāĻĻā§āϧ⧃āϤ āĻ•āϰ⧇, āϝāĻž āĻ…āĻ¨ā§āϤāĻ°ā§āϭ⧁āĻ•ā§āϤ āĻ•āϰ⧇:

  • āĻ•ā§āϞāĻžāϏāĻŋāĻ•ā§āϝāĻžāϞ āĻĢāϞāĻžāĻĢāϞ: āĻĄāĻŋāϰāĻžāĻ•, āĻŦāĻ¨ā§āĻĄāĻŋ, āĻ­āĻ¸ā§ āĻāĻŦāĻ‚ āĻ…āĻ¨ā§āϝāĻĻ⧇āϰ āĻŽā§ŒāϞāĻŋāĻ• āĻ•āĻžāϜ
  • āϏāĻžāĻŽā§āĻĒā§āϰāϤāĻŋāĻ• āωāĻ¨ā§āύāϝāĻŧāύ: āĻĢā§‹āĻŽāĻŋāύ āĻāĻŦāĻ‚ āĻ…āĻ¨ā§āϝāĻĻ⧇āϰ āĻ…ā§āϝāĻžāϞāĻ—āϰāĻŋāĻĻāĻŽ āĻ—āĻŦ⧇āώāĻŖāĻž, āĻĢāĻŋāωāϰ⧇āĻĄāĻŋ āĻāĻŦāĻ‚ āĻ…āĻ¨ā§āϝāĻĻ⧇āϰ āĻ¸ā§āĻĨāĻŋāϤāĻŋāĻļā§€āϞāϤāĻž āϤāĻ¤ā§āĻ¤ā§āĻŦ
  • āϏāĻŽā§āĻĒāĻ°ā§āĻ•āĻŋāϤ āĻ•ā§āώ⧇āĻ¤ā§āϰ: āĻŦāĻ°ā§āĻŖāĻžāϞ⧀ āĻ—ā§āϰāĻžāĻĢ āϤāĻ¤ā§āĻ¤ā§āĻŦ, āϟ⧁āϰāĻžāύ āϤāĻ¤ā§āĻ¤ā§āĻŦ⧇āϰ āϏāĻŽā§āĻĒāĻ°ā§āĻ•āĻŋāϤ āĻ•āĻžāϜ

āϏāĻžāĻŽāĻ—ā§āϰāĻŋāĻ• āĻŽā§‚āĻ˛ā§āϝāĻžāϝāĻŧāύ: āĻāϟāĻŋ āĻāĻ•āϟāĻŋ āωāĻšā§āϚ āĻŽāĻžāύ⧇āϰ āϤāĻžāĻ¤ā§āĻ¤ā§āĻŦāĻŋāĻ• āĻ—āĻŖāĻŋāϤ āĻĒāĻ¤ā§āϰ, āϝāĻž āĻāĻ•āϟāĻŋ āϗ⧁āϰ⧁āĻ¤ā§āĻŦāĻĒā§‚āĻ°ā§āĻŖ āϚāϰāĻŽ āĻ—ā§āϰāĻžāĻĢ āϤāĻ¤ā§āĻ¤ā§āĻŦ āϏāĻŽāĻ¸ā§āϝāĻž āϏāĻŽā§āĻĒā§‚āĻ°ā§āĻŖāĻ­āĻžāĻŦ⧇ āϏāĻŽāĻžāϧāĻžāύ āĻ•āϰ⧇āĨ¤ āϝāĻĻāĻŋāĻ“ āĻĒā§āϰāϝ⧁āĻ•ā§āϤāĻŋāĻ—āϤāĻ­āĻžāĻŦ⧇ āĻļāĻ•ā§āϤāĻŋāĻļāĻžāϞ⧀, āϤāĻžāĻ¤ā§āĻ¤ā§āĻŦāĻŋāĻ• āĻ…āĻŦāĻĻāĻžāύ āωāĻ˛ā§āϞ⧇āĻ–āϝ⧋āĻ—ā§āϝ, āĻĒāĻĻā§āϧāϤāĻŋ āωāĻĻā§āĻ­āĻžāĻŦāύ⧀, āĻāĻŦāĻ‚ āĻĢāϞāĻžāĻĢāϞ āϏāĻŽā§āĻĒā§‚āĻ°ā§āĻŖāĨ¤ āĻĒāĻ¤ā§āϰāϟāĻŋ āĻļ⧁āϧ⧁āĻŽāĻžāĻ¤ā§āϰ āϚāϰāĻŽ āĻ—ā§āϰāĻžāĻĢ āϤāĻ¤ā§āĻ¤ā§āĻŦ⧇āϰ āωāĻ¨ā§āύāϝāĻŧāύ āĻāĻ—āĻŋāϝāĻŧ⧇ āύāĻŋāϝāĻŧ⧇ āϝāĻžāϝāĻŧ āύāĻž, āĻŦāϰāĻ‚ āϏāĻŽā§āĻĒāĻ°ā§āĻ•āĻŋāϤ āĻ…ā§āϝāĻžāϞāĻ—āϰāĻŋāĻĻāĻŽ āĻāĻŦāĻ‚ āĻĒā§āϰāϝāĻŧā§‹āĻ— āϏāĻŽāĻ¸ā§āϝāĻžāϰ āϜāĻ¨ā§āϝ āϤāĻžāĻ¤ā§āĻ¤ā§āĻŦāĻŋāĻ• āϏāĻšāĻžāϝāĻŧāϤāĻž āĻĒā§āϰāĻĻāĻžāύ āĻ•āϰ⧇āĨ¤