Grafs, amics i coneguts Autors/ores Cristina Dalfó Miquel A. Fiol Resum Com és ben sabut, un graf és un objecte matemàtic que modelitza l'existència d'una certa relació entre parells d'elements d'un conjunt donat. Aleshores, és natural que molts dels primers resultats sobre grafs facin referència a relacions entre persones o grups de persones. En aquest article, comentem quatre resultats d'aquest tipus, els quals tenen relació amb diverses teories generals de grafs i les seves aplicacions: el lema de les encaixades de mans (relacionat amb la coloració de grafs i l'àlgebra booleana), un lema sobre els coneguts i desconeguts en una festa (amb la teoria de Ramsey), un lema sobre els amics en comú (amb la distància-regularitat i la teoria de codis) i el teorema de les noces de Hall (amb la connectivitat de les xarxes). Aquestes quatre àrees de la teoria de grafs, amb problemes sovint fàcils de plantejar però molt difícils de resoldre, s'han desenvolupat extensament i actualment són motiu de nombrosos treballs de recerca. Com a exemples de resultats i problemes representatius d'aquestes àrees, els quals són motiu de discussió en aquest treball que presentem, podem citar els següents: el teorema dels quatre colors (T4C), els nombres de Ramsey, els problemes d'existència de grafs distància-regulars i de codis completament regulars i, finalment, l'estudi de les propietats topològiques de les xarxes d'interconnexió. Descàrregues Text complet Publicat 2010-09-29 Com citar Dalfó, C., & Fiol, M. A. (2010). Grafs, amics i coneguts. Butlletí De La Societat Catalana De Matemàtiques, 25(1), 5–29. Retrieved from https://revistes.iec.cat/index.php/BSCM/article/view/62448.001 Més formats de citació ACM ACS APA ABNT Chicago Harvard IEEE MLA Turabian Vancouver Descarregar citació Endnote/Zotero/Mendeley (RIS) BibTeX Número Vol. 25 Núm. 1 (2010) Secció Articles Llicència La propietat intel·lectual dels articles és dels respectius autors. Els autors en el moment de lliurar els articles a la revista Butlletí de la Societat Catalana de Matemàtiques per a sol·licitar-ne la publicació accepten els termes següents: Els autors cedeixen a la Societat Catalana de Matemàtiques (filial de l’Institut d’Estudis Catalans) els drets de reproducció, comunicació pública i distribució dels articles presentats per a ser publicats a la revista Butlletí de la Societat Catalana de Matemàtiques. Els autors responen davant la Societat Catalana de Matemàtiques, de l'autoria i l'originalitat dels articles presentats. És responsabilitat dels autors l’obtenció dels permisos per a la reproducció de tot el material gràfic inclòs en els articles. La Societat Catalana de Matemàtiques, està exempta de tota responsabilitat derivada de l’eventual vulneració de drets de propietat intel·lectual per part dels autors. Els continguts publicats a la revista estan subjectes —llevat que s’indiqui el contrari en el text o en el material gràfic— a una llicència Reconeixement - No comercial - Sense obres derivades 3.0 Espanya (by-nc-nd) de Creative Commons, el text complet de la qual es pot consultar a https://creativecommons.org/licenses/by-nc-nd/3.0/es/deed.ca. Així doncs, s’autoritza el públic en general a reproduir, distribuir i comunicar l’obra sempre que se’n reconegui l’autoria i l’entitat que la publica i no se’n faci un ús comercial ni cap obra derivada. La revista Butlletí de la Societat Catalana de Matemàtiques no es fa responsable de les idees i opinions exposades pels autors dels articles publicats.