با توجه به تعریف ریاضیاتی نظریهٔ گراف ها، برچسب گذاری یک گراف نسبت دادن برچسب هایی به یال های گراف، یا به راس های گراف یا به هر دوی آن ها است که به صورت معمول این برچسب ها را با اعداد صحیح نمایش می دهند.
به بیان رسمی، برای یک گراف G ، منظور از برچسب گذاری شدهٔ راسی، یک تابع است که رأس های گراف G را به مجموعه ای از برچسب ها می نگارد. به گرافی که برای آن چنین تابعی تعریف شده باشد یک گراف برچسب گذاری شدهٔ راسی می گویند. به همین ترتیب، یک برچسب گذاری ِیالی یک تابع از یال های گراف به مجموعه ای از برچسب هاست، که در این حالت گراف را برچسب گذاری شدهٔ یالی نام گذاری کرده اند. اگر برچسب های نگاشته شده به یال های گراف اعضای یه مجموعهٔ مرتب باشند ( برای مثال مجموعهٔ اعداد حقیقی ) ، گراف را یک گراف وزن دار نیز می نامند.
اگر توضیحات بیشتری داده نشده باشد، عبارت گراف برچسب گذاری شده به صورت معمول به گراف برچسب گذاری شدهٔ راسی ای با برچسب های متفاوت اطلاق می شود. چنین گرافی را می توان به صورت معادل با اعداد صحیح متوالی از ۱ تا n، n تعداد یال های گراف، برچسب گذاری کرد. برای بسیاری از کاربردها، برچسب ها به گونه ای به یال ها و رأس ها نسبت داده می شوند که در حوزهٔ مربوطه معنادار باشند. برای مثال، ممکن است وزن نسبت داده شده به هر یال نمایش دهندهٔ هزینهٔ حرکت میان دو راس اطراف یال باشد. در تعریف بالا، یک گراف به عنوان یک گراف سادهٔ بدون سوی متناهی در نظر گرفته شده است. با این حال، مفهوم برچسب گذاری می تواند برای انواع مختلف گراف به کار رود. برای مثال، در نظریهٔ آتوماتا و نظریهٔ زبان رسمی بهتر است که گراف هایی چندگانه و برچسب گذاری شده در نظر گرفت، برای مثال گرافی که هر دو راس آن می تواند توسط چند یال برچسب گذاری شده به هم وصل شده باشد.
ریشهٔ بیشتر برچسب گذاری های گراف به روش های برچسب گذاریی باز می گردد که آلکسا رز در سال ۱۹۶۷ در مقالهٔ خود ارائه کرد. رزا سه نوع برچسب گذاری را مشخص کرد و آن ها رابرچسب گذاری α - , β - و ρ نامید. برچسب گذاری بتا، بعدها توسط گولومب به برچسب گذاری دلپذیر تغییر نام یافت و از آن موقع این نام شهرت یافت.
یک گراف را در صورتی «گراف دلپذیر» می نامیم که رئوس آن با اعداد بین ۰ تا ‖ E ‖ ، اندازهٔ گراف، برچسب گذاری شده و همچنین یال هایش به صورتی با اعداد بین ۱ تا ‖ E ‖ برچسب گذاری شده باشند که برچسب هر یال درست برابر قدر مطلق تفاوت برچسب های دو راس اطراف آن یال باشد. به عبارت دیگر، اگر e دو راس با برچسب های k و j را به هم وصل کرده باشد، برچسب e ‖ k − j ‖ می شود. بنابراین، یک گراف ( G := ( V , E یک گراف دلپذیرست اگر و فقط اگر تابع یک به یکی وجود داشته باشد که بین ‖ E ‖ و اعداد صحیح مثبت کوچکتر مساوی ‖ E ‖ تناظر یک به یک برقرار کند.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفبه بیان رسمی، برای یک گراف G ، منظور از برچسب گذاری شدهٔ راسی، یک تابع است که رأس های گراف G را به مجموعه ای از برچسب ها می نگارد. به گرافی که برای آن چنین تابعی تعریف شده باشد یک گراف برچسب گذاری شدهٔ راسی می گویند. به همین ترتیب، یک برچسب گذاری ِیالی یک تابع از یال های گراف به مجموعه ای از برچسب هاست، که در این حالت گراف را برچسب گذاری شدهٔ یالی نام گذاری کرده اند. اگر برچسب های نگاشته شده به یال های گراف اعضای یه مجموعهٔ مرتب باشند ( برای مثال مجموعهٔ اعداد حقیقی ) ، گراف را یک گراف وزن دار نیز می نامند.
اگر توضیحات بیشتری داده نشده باشد، عبارت گراف برچسب گذاری شده به صورت معمول به گراف برچسب گذاری شدهٔ راسی ای با برچسب های متفاوت اطلاق می شود. چنین گرافی را می توان به صورت معادل با اعداد صحیح متوالی از ۱ تا n، n تعداد یال های گراف، برچسب گذاری کرد. برای بسیاری از کاربردها، برچسب ها به گونه ای به یال ها و رأس ها نسبت داده می شوند که در حوزهٔ مربوطه معنادار باشند. برای مثال، ممکن است وزن نسبت داده شده به هر یال نمایش دهندهٔ هزینهٔ حرکت میان دو راس اطراف یال باشد. در تعریف بالا، یک گراف به عنوان یک گراف سادهٔ بدون سوی متناهی در نظر گرفته شده است. با این حال، مفهوم برچسب گذاری می تواند برای انواع مختلف گراف به کار رود. برای مثال، در نظریهٔ آتوماتا و نظریهٔ زبان رسمی بهتر است که گراف هایی چندگانه و برچسب گذاری شده در نظر گرفت، برای مثال گرافی که هر دو راس آن می تواند توسط چند یال برچسب گذاری شده به هم وصل شده باشد.
ریشهٔ بیشتر برچسب گذاری های گراف به روش های برچسب گذاریی باز می گردد که آلکسا رز در سال ۱۹۶۷ در مقالهٔ خود ارائه کرد. رزا سه نوع برچسب گذاری را مشخص کرد و آن ها رابرچسب گذاری α - , β - و ρ نامید. برچسب گذاری بتا، بعدها توسط گولومب به برچسب گذاری دلپذیر تغییر نام یافت و از آن موقع این نام شهرت یافت.
یک گراف را در صورتی «گراف دلپذیر» می نامیم که رئوس آن با اعداد بین ۰ تا ‖ E ‖ ، اندازهٔ گراف، برچسب گذاری شده و همچنین یال هایش به صورتی با اعداد بین ۱ تا ‖ E ‖ برچسب گذاری شده باشند که برچسب هر یال درست برابر قدر مطلق تفاوت برچسب های دو راس اطراف آن یال باشد. به عبارت دیگر، اگر e دو راس با برچسب های k و j را به هم وصل کرده باشد، برچسب e ‖ k − j ‖ می شود. بنابراین، یک گراف ( G := ( V , E یک گراف دلپذیرست اگر و فقط اگر تابع یک به یکی وجود داشته باشد که بین ‖ E ‖ و اعداد صحیح مثبت کوچکتر مساوی ‖ E ‖ تناظر یک به یک برقرار کند.
wiki: برچسب گذاری گراف