கலப்புக் கோட்டுரு
[[File:Mixed Graph Example.jpg|thumbnail|கலப்புக் கோட்டுரு]]
 திசையற்ற மற்றும் திசையுள்ள விளிம்புகளைக் கொண்ட [[கோட்டுரு (கணிதம்)|கோட்டுருவானது]] '''கலப்புக் கோட்டுரு''' (''mixed graph'') என அழைக்கப்படும். படத்திலுள்ள கலப்புக் கோட்டுருவின் மூன்று விளிம்புகளில் இரண்டு திசை விளிம்புகளாகவும் ஒன்று திசையற்ற விளிம்பாகவும் இருப்பதைக் காணலாம். 
 
 ==வரையறை==
 கலப்புக் கோட்டுரு ''G'' = (''V'', ''E'', ''A'') என்ற மும்மையாகும். இதில்&lt;ref name=&quot;BeckBladoCrawfordJeanLouisYoung&quot;&gt;{{harvtxt|Beck|Blado|Crawford|Jean-Louis|2013|p=1}}&lt;/ref&gt;:
 * &lt;math&gt;V&lt;/math&gt; - [[கணு (கோட்டுருவியல்)|முனைகளின்]] [[கணம் (கணிதம்)|கணம்]];
 * &lt;math&gt;E&lt;/math&gt; - திசையற்ற விளிம்புகளின் கணம் 
 * &lt;math&gt;A&lt;/math&gt; - திசை விளிம்புகளின் கணம்
 
 கலப்புக் கோட்டுருவில் &lt;math&gt;u,v \in V&lt;/math&gt; இரு அண்மை முனைகள் எனில்: 
 *இவ்விரு முனைகளை இணைக்கும் ''திசை விளிம்பு'' (directed edge) அல்லது ''வில்'' (arc) என்பது திசைப்போக்குடைய விளிம்பாகும். இதன் குறியீடுகள்: &lt;math&gt;\overrightarrow{uv}&lt;/math&gt; அல்லது &lt;math&gt;(u,v)&lt;/math&gt;. இதில் &lt;math&gt;u&lt;/math&gt; வில்லின் வால்முனை;  &lt;math&gt;v&lt;/math&gt; தலைமுனை.&lt;ref name=&quot;Ries&quot;&gt;{{harvtxt|Ries|2007|p=1}}&lt;/ref&gt; 
 *இவ்விரு முனைகளை இணைக்கும் திசையற்ற விளிம்பு (''undirected edge'') அல்லது சுருக்கமாக விளிம்பு (edge) என்பது திசைப்போக்கற்ற விளிம்பாகும். இதன் குறியீடுகள்: &lt;math&gt;uv&lt;/math&gt; or &lt;math&gt;[u,v]&lt;/math&gt;.&lt;ref name=&quot;Ries&quot; /&gt;
 
 கலப்புக் கோட்டுருவில் [[பாதை (கோட்டுருவியல்)|நடை]] என்பது &lt;math&gt;v_0,c_1,v_1,c_2,v_2,\dots,c_k,v_k&lt;/math&gt; என்ற முனைகள் மற்றும் விளிம்புகளின் தொடர்முறையாகும். இத்தொடர்முறையில் &lt;math&gt;v_0,,v_1,,v_2,\dots,v_k&lt;/math&gt; கலப்புக் கோட்டுருவின் முனைகள்; மேலும் அனைத்து &lt;math&gt;i&lt;/math&gt; களுக்கும் &lt;math&gt;c_i=v_{i}v_{i+1}&lt;/math&gt; என்பது கலப்புக் கோட்டுருவின் விளிம்பாகவோ அல்லது &lt;math&gt;c_i=\overrightarrow{v_{i}v_{i+1}}&lt;/math&gt; திசைவிளிம்பாகவோ இருக்கும். முதல் மற்றும் இறுதி முனைகள் தவிர வேறெந்த  முனைகளோ, விளிம்புகளோ அல்லது விற்களோ மீண்டும் வராத [[பாதை (கோட்டுருவியல்)|பாதை]]யானது &quot;நடை&quot; எனப்படுகிறது. முதல் மற்றும் இறுதி முனைகள் இரண்டும் ஒரே முனையாக அமைந்தால் அப்பாதையானது &quot;மூடிய பாதை&quot;யாகும். முதல் மற்றும் இறுதி முனைகளைத் தவிர வேறெந்த முனைகளும் மீண்டும் வராத மூடிய பாதையானது [[சுழற்சி (கோட்டுருவியல்)|சுழற்சி]]யாகும். ஒரு கலப்புக் கோட்டுருவில் சுழற்சிகளே இல்லையெனில் அது &quot;சுழற்சியற்றக் கலப்புக் கோட்டுரு&quot; என அழைக்கப்படும்.
 
 == நிறந்தீட்டல் ==
 கலப்புக் கோட்டுருவிற்கு நிறந்தீட்டலை அதன் முனைகளுக்கு பெயரிடலாக அல்லது வெவ்வேறு {{mvar|k}} (நேர் முழு எண்) நிறங்களை அதன் முனைகளுக்கு அளிப்பதாகவோ எடுத்துக்கொள்ளலாம்.&lt;ref name=&quot;HansenKuplinskydeWerra&quot;&gt;{{harvtxt|Hansen|Kuplinsky|de Werra|1997|p=1}}&lt;/ref&gt; விளிம்புகளால் இணைக்கப்படும் முனைகள் ஒவ்வொன்றுக்கும் வெவ்வேறு நிறங்கள் தரப்பட வேண்டும். அளிக்கப்படும் நிறங்கள் {{math|1}} முதல் {{mvar|k}} வரையான எண்களால் குறிக்கப்பட வேண்டும். ஒரு திசை விளிம்பில் அதன் வால்முனைக்கு அளிக்கப்படும் எண் அதன் தலைமுனைக்கு அளிக்கப்படும் எண்ணைவிட சிறியதாக இருக்குமாறு கலப்புக் கோட்டுவை நிறந்தீட்ட வேண்டும்.&lt;ref name=&quot;HansenKuplinskydeWerra&quot; /&gt;
 
 === எடுத்துக்காட்டு ===
 [[File:ColoredMixed.png|thumbnail|கலப்புக் கோட்டுரு நிறந்தீட்டல்]]
 அருகிலுள்ள படத்தில் ஒரு கலப்புக் கோட்டுருவின் முனைகளுக்கு எண்கள் தரப்பட்டு நிறந்தீட்டப்பட்டுள்ளது. இக்கோட்டுருவிற்கு நிறந்தீட்ட எடுத்துக்கொள்ளப்பட்ட எண்கள் &lt;math&gt;\{1,2,3\}&lt;/math&gt;. &lt;math&gt;u&lt;/math&gt; மற்றும் &lt;math&gt;v&lt;/math&gt; முனைகள் விளிம்பால் இணைக்கப்பட்டிருப்பதால் அவற்றுக்கு மாறுபட்ட நிறங்கள் அல்லது எண்கள் அளிக்கப்பட வேண்டும். அவற்றுக்கு முறையே 1, 2 என்ற எண்கள் அளிக்கப்பட்டுள்ளன. &lt;math&gt;v&lt;/math&gt; மற்றும் &lt;math&gt;w&lt;/math&gt; இரண்டும் ஒரு வில்லால் இணைக்கப்பட்டுள்ளன. எனவே வால் முனைக்கு (&lt;math&gt;v&lt;/math&gt;) சிறிய எண்ணும் தலைமுனைக்கு (&lt;math&gt;w&lt;/math&gt;) பெரிய எண்ணும் அளிக்கப்பட வேண்டும். &lt;math&gt;v,&lt;/math&gt; &lt;math&gt;w&lt;/math&gt; இரண்டுக்கும் முறையே 2, 3 என்ற எண்கள் அளிக்கப்பட்டுள்ளன.
 
 === நிறந்தீட்டல் இருத்தல்===
 ஒரு கலப்புக் கோட்டுருவை நிறந்தீட்ட முடியலாம் அல்லது முடியாமலும் இருக்கலாம். ஒரு கலப்புக் கோட்டுருவில் திசையுள்ள சுழற்சிகள் இல்லாமல் இருந்தால் மட்டுமே அக்கோட்டுருவிற்கு k-நிறந்தீட்டல் இருக்கும்.&lt;ref name=&quot;Ries&quot; /&gt; அவ்வாறு ஒரு k-நிறந்தீட்டல் இருக்கும்பட்சத்தில் அக்கலப்புக் கோட்டுருவை முறையாக நிறந்தீட்டத் தேவைப்படும் k இன் மிகச்சிறிய மதிப்பு, கோட்டுருவின் [[நிற எண்]] எனப்படும். நிற எண்ணின் குறியீடு &lt;math&gt;\chi(G)&lt;/math&gt; ஆகும்.&lt;ref name=&quot;Ries&quot; /&gt; முறையாக k-நிறந்தீட்டக்கூடிய எண்ணிக்கையை k இன் பல்லுறுப்புக்கோவைச் சார்பாகக் காணலாம். இப்பல்லுறுப்புக்கோவை அக்கலப்புக் கோட்டுருவின் &quot;நிறப் பல்லுறுப்புக்கோவை&quot; என்றழைக்கப்படும்; இதன் குறியீடு &lt;math&gt;\chi_G(k)&lt;/math&gt; ஆகும்.&lt;ref name=&quot;BeckBladoCrawfordJeanLouisYoung&quot; /&gt;
 
 
 == குறிப்புகள் ==
 {{reflist}}
 
 == மேற்கோள்கள் ==
 *{{citation
  | last1 = Beck | first1 = M.
  | last2 = Blado | first2 = D.
  | last3 = Crawford | first3 = J.
  | last4 = Jean-Louis | first4 = T.
  | last5 = Young | first5 = M. 
  | doi = 10.1007/s00373-013-1381-1
  | journal = Graphs and Combinatorics
  | title = On weak chromatic polynomials of mixed graphs
  | year = 2013| arxiv = 1210.4634}}.
 *{{citation |last1= Cowell |first1= Robert G. |last2= Dawid |first2= A. Philip|author2-link=Philip Dawid |last3= Lauritzen |first3= Steffen L.|author3-link=Steffen Lauritzen |last4= Spiegelhalter |first4= David J.|author4-link=David Spiegelhalter |title= Probabilistic Networks and Expert Systems: Exact Computational Methods for Bayesian Networks |publisher= Springer-Verlag New York |year= 1999 |isbn= 0-387-98767-3|page=27|url=https://books.google.com/books?id=G_4E_w_wJzcC&amp;pg=PA27|doi=10.1007/0-387-22630-3}}
 *{{citation
  | last1 = Hansen | first1 = Pierre
  | last2 = Kuplinsky | first2 = Julio
  | last3 = de Werra | first3 = Dominique
  | doi = 10.1007/BF01194253
  | issue = 1
  | journal = Mathematical Methods of Operations Research
  | mr = 1435900
  | pages = 145–160
  | title = Mixed graph colorings
  | volume = 45
  | year = 1997}}.
 *{{citation
  | last = Ries | first = B.
  | doi = 10.1016/j.dam.2006.05.004
  | issue = 1
  | journal = Discrete Applied Mathematics
  | mr = 2281351
  | pages = 1–6
  | title = Coloring some classes of mixed graphs
  | volume = 155
  | year = 2007}}.
 
 ==வெளியிணைப்புகள்==
 *{{mathworld|id=MixedGraph|title=Mixed Graph}}